具有多个数的欧几里得算法(GCD)？

Question

所以我正在用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))

Answer 1

由于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在reduce确保您的递归函数最多一次(因为len(numbers) > 2只在原来的调用),它具有永不溢出堆栈中的额外的好处.

Answer 2

你可以使用reduce:

>>> from fractions import gcd
>>> reduce(gcd,(30,40,60))
10

相当于;

>>> lis = (30,40,60,70)
>>> res = gcd(*lis[:2])  #get the gcd of first two numbers
>>> for x in lis[2:]:    #now iterate over the list starting from the 3rd element
...    res = gcd(res,x)

>>> res
10

帮助上reduce:

>>> reduce?
Type:       builtin_function_or_method
reduce(function, sequence[, initial]) -> value

Apply a function of two arguments cumulatively to the items of a sequence,
from left to right, so as to reduce the sequence to a single value.
For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
((((1+2)+3)+4)+5).  If initial is present, it is placed before the items
of the sequence in the calculation, and serves as a default when the
sequence is empty.

Answer 3

Python 3.9引入了多参数版本math.gcd，因此您可以使用：

import math
math.gcd(30, 40, 36)

3.5 <= Python <= 3.8.x：

import functools
import math
functools.reduce(math.gcd, (30, 40, 36))

3 <= Python < 3.5：

import fractions
import functools
functools.reduce(fractions.gcd, (30, 40, 36))

Answer 4

PYTHON中求两个以上数字的最小公倍数的解决方案如下：

#finding LCM (Least Common Multiple) of a series of numbers

def GCD(a, b):
    #Gives greatest common divisor using Euclid's Algorithm.
    while b:      
        a, b = b, a % b
    return a

def LCM(a, b):
    #gives lowest common multiple of two numbers
    return a * b // GCD(a, b)

def LCMM(*args):
    #gives LCM of a list of numbers passed as argument 
    return reduce(LCM, args)

这里我在range()函数的最后一个参数中添加了 +1，因为函数本身从零 (0) 开始到 n-1。单击超链接了解有关range()函数的更多信息：

print ("LCM of numbers (1 to 5) : " + str(LCMM(*range(1, 5+1))))
print ("LCM of numbers (1 to 10) : " + str(LCMM(*range(1, 10+1))))
print (reduce(LCMM,(1,2,3,4,5)))

那些不熟悉 python 的人可以通过给定的链接阅读有关reduce()函数的更多信息。