具有多个数字的欧几里德算法(GCD)? [英] Euclidean algorithm (GCD) with multiple numbers?
问题描述
所以我正在用 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.
这篇关于具有多个数字的欧几里德算法(GCD)?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!