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

发布时间：2020-12-20 10:33:44 所属栏目：Python 来源：网络整理

导读：所以我正在用 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,

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

解决方法

由于GCD是关联的,因此GCD(a,b,c,d)与GCD(GCD(a,b),c),d)相同.在这种情况下,Python的 reduce函数将是减少len(数字)>的情况的良好候选者. 2进行简单的2位数比较.代码看起来像这样：

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

Reduce将给定的函数应用于列表中的每个元素,以便类似

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

和做的一样

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

现在唯一剩下的就是在len(数字)< = 2时编码.在reduce中只向GCD传递两个参数,确保你的函数最多只能递归一次(因为len(数字)> 2仅在原始调用中),它具有永不溢出堆栈的额外好处.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!