[已解决]欧几里得算法

raorr

def gcd(x, y):
    while y:
        t = x % y
        x = y
        y = t

    return x
   
print(gcd(4, 6))

我知道我的想法肯定有错，但是我不知道正确的思路是什么，求大神指点！

下面是我看了这个代码的思路（以4，6为例）

y循环开始

t是x除以y的余数，所以t=4

x=y，所以这里是x=6？

y=t，所以y=4？

最后返回x。。。。。？



这只是我的理解，本来while循环搞得迷迷糊糊的，这整得我更晕了，原谅本垃圾吧。

最佳答案

月排行榜 / 总排行榜

qiuyouzhi

2020-6-21 10:24:18

while y是while y != 0的意思。
给你分析下代码过程：
t = x % y，t = 4
x = y,  x = 6
y = t, y = 4
y不为0，继续
t = x % y, t = 2
x = y, x = 4
y = t, y = 2
y不为0，继续
t = x % y, t = 0
x = y, x = 2
y = t, y= 0
此时y为0，退出循环，返回x，
x当前值为2，所以结果为2.

跳转到最佳答案楼层

永恒的蓝色梦想

代码没问题啊，4 和 6 的最大公因数不是 2 吗？

今天的我更强了

while y 的意思是判断是否循环的条件，y只要非零就是代表true，就会进入循环，gcd（4,6）t=4%6=4,x=6,y=4

qiuyouzhi

while y是while y != 0的意思。
给你分析下代码过程：
t = x % y，t = 4
x = y,  x = 6
y = t, y = 4
y不为0，继续
t = x % y, t = 2
x = y, x = 4
y = t, y = 2
y不为0，继续
t = x % y, t = 0
x = y, x = 2
y = t, y= 0
此时y为0，退出循环，返回x，
x当前值为2，所以结果为2.

qiuyouzhi

今天的我更强了 发表于 2020-6-21 10:23
while y 的意思是判断是否循环的条件，y只要非零就是代表true，就会进入循环，gcd（4,6）不太对吧，4小于6 ...

都一样的，gcd(6,4)和gcd(4,6)一样

今天的我更强了

qiuyouzhi 发表于 2020-6-21 10:25
都一样的，gcd(6,4)和gcd(4,6)一样

嗯嗯，我运行了一下 确实一样