python – 具有多个数字的欧几里德算法(GCD)?
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python – 具有多个数字的欧几里德算法(GCD)?,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1228字,纯文字阅读大概需要2分钟。
内容图文
所以我正在用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))
解决方法:
由于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,y]),[a,b,c,d])
和做的一样
gcd = GCD(a,b)
gcd = GCD(gcd,c)
gcd = GCD(gcd,d)
现在唯一剩下的就是在len(数字)< = 2时编码.在reduce中只向GCD传递两个参数,确保你的函数最多只能递归一次(因为len(数字)> 2仅在原始调用中) ,它具有永不溢出堆栈的额外好处.
内容总结
以上是互联网集市为您收集整理的python – 具有多个数字的欧几里德算法(GCD)?全部内容,希望文章能够帮你解决python – 具有多个数字的欧几里德算法(GCD)?所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。