小无趣 发表于 2021-1-12 19:46:09

python 欧几里算法求最大公约数

def gcd(x, y):
    if y:
      return gcd(y, x%y)
    else:
      return x
   
print(gcd(4, 6))

问题1：最大公约数的求法为啥是两个数互余，能反过来求余嘛？例：x%y，能y%x嘛？
问题2：这个程序需要咋理解，为啥当y为0的时候，返回x，是因为递归的时候当y为0的时候，最大公约数就为x了嘛？
问题3：为啥在第一个return 那里，要将y的值传给x

求大佬解答！！

昨非 发表于 2021-1-12 19:48:24

这不是数学里学的吗？
y取代x，y对x的余数取代y

小无趣 发表于 2021-1-12 19:51:49

昨非 发表于 2021-1-12 19:48
这不是数学里学的吗？
y取代x，y对x的余数取代y

对呀，我感觉我要重修了，全都忘了...
你这么一说，我好像有点理解了

昨非 发表于 2021-1-12 19:54:40

小无趣 发表于 2021-1-12 19:51
对呀，我感觉我要重修了，全都忘了...
你这么一说，我好像有点理解了

看百度辗转相除的定义https://baike.baidu.com/item/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95/1647675?fr=aladdin

昨非 发表于 2021-1-12 20:11:54

understand？

小无趣 发表于 2021-1-12 20:17:34

昨非 发表于 2021-1-12 20:11
understand？

差不多了，谢谢大佬！！{:10_266:}

昨非 发表于 2021-1-12 20:19:37

小无趣 发表于 2021-1-12 20:17
差不多了，谢谢大佬！！

不至于不至于，
主要这玩意就一概念问题
理解了定义都不难的{:10_245:}
页: [1]
查看完整版本: python 欧几里算法求最大公约数