Python求最大公约数(3)

qiuyouzhi

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))

• 更相减损术
• 优点：不需要取模，而且效率更快，代码更简洁
• 缺点：运算次数太多
  

还会继续更新！

zltzlt

简化

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))

qiuyouzhi

zltzlt 发表于 2020-3-5 12:45
简化

hif

zltzlt 发表于 2020-3-5 12:45
简化

有丶东西

永恒的蓝色梦想

优点：不需要取模，而且效率更快，代码更简洁

应该是欧几里得法快吧

qiuyouzhi

永恒的蓝色梦想 发表于 2020-4-10 20:00
应该是欧几里得法快吧

各有各的优势