所以我正在用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?
已更新,但仍无法正常工作:
updated, still not working:
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)?
发布评论