[已解决]python 欧几里算法求最大公约数

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

您需要登录才可以下载或查看，没有账号？立即注册

x

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: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
对呀，我感觉我要重修了，全都忘了...
你这么一说，我好像有点理解了

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

understand？

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

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

差不多了，谢谢大佬！！

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

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

不至于不至于，
主要这玩意就一概念问题
理解了定义都不难的

账号		自动登录	找回密码
密码			立即注册