具有多个数字的欧几里德算法(GCD)?

本文介绍了具有多个数字的欧几里德算法(GCD)?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

So I'm writing a program in Python to get the GCD of any amount of numbers.

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.但是，我不明白如何递归地使用该算法，以便它可以处理多个数字.有人可以解释一下吗?

The function takes a list of numbers. This should print 2. However, I don't understand how to use the the algorithm recursively so it can handle multiple numbers. Can someone explain?

更新了，还是不行:

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

好的，解决了

Ok, solved it

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

然后使用reduce，比如

and then use reduce, like

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

推荐答案

由于 GCD 是关联的，GCD(a,b,c,d) 与 GCD(GCD(GCD(a,b),c),d).在这种情况下，Python 的 reduce 函数将是减少 len(numbers) >2 到一个简单的 2 数比较.代码看起来像这样:

Since GCD is associative, GCD(a,b,c,d) is the same as GCD(GCD(GCD(a,b),c),d). In this case, Python's reduce function would be a good candidate for reducing the cases for which len(numbers) > 2 to a simple 2-number comparison. The code would look something like this:

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

Reduce 将给定的函数应用到列表中的每个元素，因此类似于

Reduce applies the given function to each element in the list, so that something like

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 编码.在 reduce 中仅将两个参数传递给 GCD 确保您的函数最多递归一次(因为 len(numbers) > 2 仅在原始调用)，它具有永远不会溢出堆栈的额外好处.

Now the only thing left is to code for when len(numbers) <= 2. Passing only two arguments to GCD in reduce ensures that your function recurses at most once (since len(numbers) > 2 only in the original call), which has the additional benefit of never overflowing the stack.