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

心电图

看了小甲鱼的python视频，还是不懂欧几里得算法求最大公约数的思想：欧几里得算法要求x>y时，用x%y，但是课后题的代码中没有关于x,y的大小判断依然可以正确算出最大公约数，请各位大神帮忙解释一下下面的代码，感激不尽！！！

#递归
def gcd(x, y):
    if y:
        return gcd(y, x%y)
    else:
        return x

#非递归
def gcd(x, y):
     
while y:
         
    x, y = y, x%y
     
return x

最佳答案

月排行榜 / 总排行榜

claws0n

2018-8-16 15:25:30

看非递归的方法好了，递归的也是一样
while y: 即 y 不为零，将持续循环
y = x%y   # y 是 x 对 y 取 余数。如果 y 要等于零，那必然是找到倍数关系了

其实如果不懂的话，自己展开来看
gcd(42,12)
x,y = 12, 42%12 == 6
x,y = 6, 12%12 == 0
找到啦~~ 42 与 12 的最大公约数为 6

跳转到最佳答案楼层

claws0n

看非递归的方法好了，递归的也是一样
while y: 即 y 不为零，将持续循环
y = x%y   # y 是 x 对 y 取 余数。如果 y 要等于零，那必然是找到倍数关系了

其实如果不懂的话，自己展开来看
gcd(42,12)
x,y = 12, 42%12 == 6
x,y = 6, 12%12 == 0
找到啦~~ 42 与 12 的最大公约数为 6

心电图

claws0n 发表于 2018-8-16 15:25
看非递归的方法好了，递归的也是一样
while y: 即 y 不为零，将持续循环
y = x%y   # y 是 x 对 y 取 余 ...

谢谢您的解答！

claws0n

心电图 发表于 2018-8-18 09:55
谢谢您的解答！

楼主，往后如果问题得以解决，记得采纳最佳答案哦~~

心电图

claws0n 发表于 2018-8-18 10:23
楼主，往后如果问题得以解决，记得采纳最佳答案哦~~

嗯嗯，我再等待别的回答争取理解的更透彻些