论坛 › Python交流 › Python求最大公约数(2)

qiuyouzhi 发表于 2020-3-5 12:26:42

Python求最大公约数(2)

Python 求最大公约数

2，辗转相除法（欧几里得算法）

代码：
def gcdv2(a, b):
    big = a if a > b else b
    small = a if a < b else b
    if big % small == 0:
      return small
    return gcdv2(big%small, small) # 用递归实现辗转相除

print(gcdv2(25, 5))
print(gcdv2(100, 80))
print(gcdv2(27, 14))

[*]辗转相除法
[*]优点：常用，简洁
[*]缺点：必须要取模

jackz007 发表于 2020-3-5 12:32:46

       能否解释一下，为什么说 “必须要取模” 是 "缺点"？

zltzlt 发表于 2020-3-5 12:36:47

代码可以简化

def gcdv2(a, b):
    if not (big := max(a, b)) % (small := min(a, b)):
      return small
    return gcdv2(big % small, small)# 用递归实现辗转相除


print(gcdv2(25, 5))
print(gcdv2(100, 80))
print(gcdv2(27, 14))

一个账号 发表于 2020-3-5 12:42:09

zltzlt 发表于 2020-3-5 12:36
代码可以简化

这只支持 3.8。

PS：我换头像了

zltzlt 发表于 2020-3-5 12:42:45

一个账号 发表于 2020-3-5 12:42
这只支持 3.8。

PS：我换头像了

嗯

qiuyouzhi 发表于 2020-3-5 12:43:24

jackz007 发表于 2020-3-5 12:32
能否解释一下，为什么说 “必须要取模” 是 "缺点"？

如果整数较大的话，取模运算性能会很差

qiuyouzhi 发表于 2020-3-5 12:44:09

zltzlt 发表于 2020-3-5 12:36
代码可以简化

1，只支持3.8
2，写的稍微简单一点，用于理解

永恒的蓝色梦想 发表于 2020-3-16 14:41:06

jackz007 发表于 2020-3-5 12:32
能否解释一下，为什么说 “必须要取模” 是 "缺点"？

取模效率不高

永恒的蓝色梦想 发表于 2020-4-10 20:18:08

本帖最后由 永恒的蓝色梦想 于 2020-4-10 20:26 编辑

循环效率更好def gcd(a,b):
    if a<b:
      a,b=b,a

    while b:
      a,b=b,a%b

    return a

查看完整版本: Python求最大公约数(2)