几何级数与任意数量的行

StackOverflow https://stackoverflow.com/questions/3824530

  •  26-09-2019
  •  | 
  •  

题

我可以具有任何数量的行其由2至10个号码。而从该行，我得几何级数。

例如： 鉴于数行：125 5 625我一定要得到的答案5。行：128 8 512我一定要得到的答案4

。

你能给我吗？我不要求一个计划，只是一个提示，我想自己了解它，由我自己写的代码，但该死的，我一直整天想着，可能不知道这一点。

感谢您。

<强>不写整个程序！

家伙，你不明白这一点，我不能只是简单的化妆一个部门。其实，我得到几何级数+显示所有数字。在128 8 512行的所有数字将是：8 32 128 512

有帮助吗？

解决方案

Seth的回答是正确的。我在这里离开这个答案，帮助解释为何回答128 8 512是4因为人们似乎有与麻烦。

一个几何级数的元件可以被写成如下形式c*b^n其中b是你正在寻找的数目（b也一定大于1），c是一个常数，n是一些arbritrary数。

所以，最好的办法是用最小号开始，在所有可能的解决方案因式分解它，并期待在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，候选人不会对剩余的号码工作，你必须看看下一个最小数量和它分解。所以在这里你会分解15：15 = 15*?^0（退化的情况下），15 = 3*5^1，15 = 5*3^1，15 = 1*15^1。答案是5，和3 = 3*5^0，所以它的工作原理进行。

其他提示

编辑：我觉得现在应该是正确的 的

。

该算法不依赖于保理，只对欧几里德算法，以及它们的近似变体。这使得它稍微复杂的数学然后使用保理的解决方案，但它会快很多。如果你理解了欧氏算法和对数，数学不应该是一个问题。的

（1）排序组数字。你具有的形式ab^{n1} < .. < ab^{nk}的号码。

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

（2）形成一个新的列表，其第n个第（n + 1）由第（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，1,2和6）的任何功率。问题是，我们既不知道b也不d_i。但是，如果我们让m = gcd(d_1, ... d_(k-1))，那么我们可以发现b^m，这已经足够了。

请注意：鉴于b^i和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可能不是整数。让我知道这是一个问题。

最简单的方法是因式分解的数字，发现它们共有的最大数量。但要小心，分解具有指数复杂性，所以如果你的行中获得大的数字，它可能会停止工作。

你需要的是知道所有数字的最大公约数一行。

的一种方法是，以检查是否他们都可以通过该行中的更小的数目来划分。

如果没有，请尝试半行的数量较少。

然后继续下去，直到找到一个数字，将其划分全部或者您的除数等于1。

塞特回答是不正确的，那applyin溶液不解决例如128 8 2048行（2 * 4 ^ x）中，您可以： 8 128 2048 => 16 16 => GCD = 16

这是事实，解决的办法是这种结果的一个因素，但你需要的因素，并逐一检查什么是正确的答案，在这种情况下，你将需要检查以相反的顺序16, 8, 4, 2解决方案的因素，直到你请参阅第4个匹配的所有条件。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top