具有多个数字的欧几里得算法（GCD）？

所以我正在用 Python 编写一个程序来获取任意数量的数字的 GCD。

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]


    # i'm stuck here, this is wrong
    for i in range(len(numbers)-1):
        print GCD([numbers[i+1], numbers[i] % numbers[i+1]])


print GCD(30, 40, 36)

该函数接受一个数字列表。 这应该打印 2。但是，我不明白如何递归地使用该算法，以便它可以处理多个数字。有人可以解释一下吗？

更新了，还是不行：

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]

    gcd = 0

    for i in range(len(numbers)):
        gcd = GCD([numbers[i+1], numbers[i] % numbers[i+1]])
        gcdtemp = GCD([gcd, numbers[i+2]])
        gcd = gcdtemp

    return gcd

好的，解决了

def GCD(a, b):

    if b == 0:
        return a
    else:
        return GCD(b, a % b)

然后使用reduce，比如

reduce(GCD, (30, 40, 36))

由于 GCD 是结合律，GCD(a,b,c,d)是相同的GCD(GCD(GCD(a,b),c),d)。在这种情况下，Python 的reduce函数将是减少以下情况的良好候选者：len(numbers) > 2到简单的 2 数比较。代码看起来像这样：

if len(numbers) > 2:
    return reduce(lambda x,y: GCD([x,y]), numbers)

Reduce 将给定的函数应用于列表中的每个元素，这样就像

gcd = reduce(lambda x,y:GCD([x,y]),[a,b,c,d])

和做一样

gcd = GCD(a,b)
gcd = GCD(gcd,c)
gcd = GCD(gcd,d)

现在唯一剩下的就是编写代码len(numbers) <= 2。仅传递两个参数GCD in reduce确保你的函数最多递归一次（因为len(numbers) > 2仅在原始调用中），这具有永远不会溢出堆栈的额外好处。