4

我可以有任何数字行，其中包含 2 到 10 个数字。从这一行开始，我必须得到几何级数。

例如：给定数字行：125 5 625我必须得到答案5。行：128 8 512我必须得到答案4。

你能帮我个忙吗？我不求程序，只是一个提示，我想自己看懂，自己写代码，但是该死的，我想了一天也想不通。

谢谢你。

不要编写整个程序！

伙计们，你不明白，我不能简单地划分。我实际上必须得到几何级数+显示所有数字。在行中128 8 512，所有数字将是：8 32 128 512

4

5 回答 5

4

赛斯的答案是正确的。我将这个答案留在这里，以帮助详细说明为什么答案128 8 512是4因为人们似乎对此有问题。

几何级数的元素可以写成你正在寻找的数字（c*b^n也必须大于 1），是一个常数并且是一些任意数字。bbcn

所以最好的办法是从最小的数字开始，分解它并查看所有可能的解决方案，将它写在c*b^n表格中，然后b在剩余的数字上使用它。返回有效的最大结果。

所以对于你的例子：

125 5 625

从 5 开始。5 是素数，所以它只能写成一种方式：5 = 1*5^1. 所以你b是 5。你现在可以停下来，假设你知道该行实际上是几何的。如果您需要确定它是否是几何图形，b请在剩余的数字上进行测试。

128 8 512

8可以写成不止一种方式：8 = 1*8^1, 8 = 2*2^2, 8 = 2*4^1, 8 = 4*2^1. 所以你有三个可能的值b，还有几个不同的选项c。先尝试最大的。8不起作用。试试4。有用！128 = 2*4^3和512 = 2*4^4。b也是如此。4_ c_2

3 15 375

这个有点意思，因为第一个数字是素数但不是b，它是c。因此，您需要确保如果您的第一个b-candidate 不适用于剩余的数字，您必须查看下一个最小的数字并将其分解。所以在这里你会分解 15: 15 = 15*?^0(退化的情况), 15 = 3*5^1, 15 = 5*3^1, 15 = 1*15^1. 答案是 5 和3 = 3*5^0，所以它成功了。

于 2010-09-29T18:15:55.513 回答
2

编辑：我认为这现在应该是正确的。

该算法不依赖于因式分解，仅依赖于欧几里得算法及其紧密变体。这使得它在数学上比使用因式分解的解决方案稍微复杂一些，但它会快得多。如果您了解欧几里得算法和对数，那么数学应该不是问题。

(1) 对数字集进行排序。你有表格的数字ab^{n1} < .. < ab^{nk}。

例子：(3 * 2, 3*2^5, 3*2^7, 3*2^13)

(2) 形成一个新列表，其排序列表的第 (n+1) 个元素的第 n 个元素除以第 (n) 个。你现在有b^{n2 - n1}, b^{n3 - n2}, ..., b^{nk - n(k-1)}.

（续）示例：(2^4, 2^2, 2^6)

定义d_i = n_(i+1) - n_i（不要编程——即使你想也不能，因为n_i未知——这只是为了解释程序是如何工作的）。

（续）示例：d_1 = 4, d_2 = 2, d_3 = 6

请注意，在我们的示例问题中，我们可以自由选择(a = 3, b = 2)或(a = 3/2, b = 4)。底线是b从步骤（2）中划分列表中所有条目的“真实”的任何幂是正确的答案。因此，我们可以提高b到任何除以所有的幂d_i（在这种情况下，任何除以 4、2 和 6 的幂）。问题是我们既不知道b也不知道d_i。但是如果我们让m = gcd(d_1, ... d_(k-1))，那么我们可以找到b^m，这就足够了。

注意：给定b^iand b^j，我们可以找到b^gcd(i, j)使用：

log(b^i) / log(b^j) = (i log b) / (j log b) = i/j

这允许我们使用欧几里得算法的修改版本来查找b^gcd(i, j). “动作”全部在指数中：加法已被乘法，乘以幂，以及（因此）商与对数代替：

import math
def power_remainder(a, b):
    q = int(math.log(a) / math.log(b))
    return a / (b ** q)        

def power_gcd(a, b):
    while b != 1:
    a, b = b, power_remainder(a, b)
    return a

(3) 由于原始集合的所有元素的幂不同r = b^gcd(d_1, ..., d_(k-1))，因此它们都是cr^n所需的形式。但是，c可能不是整数。让我知道这是否有问题。

于 2010-09-29T18:41:48.847 回答
0

最简单的方法是分解数字并找到它们共有的最大数字。但要小心，因式分解具有指数级的复杂性，因此如果您在行中获得大量数字，它可能会停止工作。

于 2010-09-29T18:14:03.143 回答
0

你想要的是知道连续所有数字的最大公约数。

一种方法是检查它们是否都可以除以行中较小的数字。

如果没有，请尝试该行中较小数字的一半。

然后继续往下走，直到找到一个将它们整除或除数等于 1 的数字。

于 2010-09-29T18:15:10.317 回答
0

Seth 答案不正确，应用该解决方案不能解决128 8 2048行，例如 (2*4^x)，你得到： 8 128 2048=> 16 16=> GCD = 16

确实，解决方案是此结果的一个因素，但您需要将其分解并一一检查正确答案是什么，在这种情况下，您需要以相反的顺序检查解决方案因素，16, 8, 4, 2直到您看到 4 个匹配所有条件。

于 2010-09-29T22:00:03.393 回答