Python求最大公约数(3)
Python 求最大公约数3,更相减损术：
思路：
这个方法应该很多鱼油都没有听过，我来讲讲原理：
两个正整数a和b(a > b)， 他们的最大公约数等于a-b的差值c
和较小数b的最大公约数。例如10和25,25减10的差是15，那么10和25的最大公约数
就等于10和15的最大公约数。
代码：
def gcdv3(a, b):
if a == b:
return a
big = a if a > b else b
small = a if a < b else b
return gcdv3(big - small, small)
print(gcdv3(25, 5))
print(gcdv3(100, 80))
print(gcdv3(27, 14))
[*]更相减损术
[*]优点：不需要取模，而且效率更快，代码更简洁
[*]缺点：运算次数太多
还会继续更新！ 简化
def gcdv3(a, b):
return gcdv3(max(a, b) - min(a, b), min(a, b)) if a != b else a
print(gcdv3(25, 5))
print(gcdv3(100, 80))
print(gcdv3(27, 14)) zltzlt 发表于 2020-3-5 12:45
简化
{:10_256:} zltzlt 发表于 2020-3-5 12:45
简化
有丶东西 优点：不需要取模，而且效率更快，代码更简洁应该是欧几里得法快吧 永恒的蓝色梦想 发表于 2020-4-10 20:00
应该是欧几里得法快吧
各有各的优势
页:
[1]