[已解决]第17讲的 最大公约数

xia3880417

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

    return x
   
print(gcd(4, 6))



为什么这里不用判断x  y的大小。
测试的时候x%y 只能大的在前 小的在后

最佳答案

月排行榜 / 总排行榜

heidern0612

2018-12-10 17:31:53

1. 
   
2. def gcd(x, y):
   
3.     while y:     #y不为零时，开始循环;
   
4.         t = x % y  #一次循环，t =53 % 17 ,余数为2, t = 2;二次循环， t = 17/%2 = 1;三次循环，t = 2% 1 = 0;
   
5.         x = y        #一次循环，x = 17 ;二次循环，x = 2;三次循环 x = 1
   
6.         y = t        # 一次循环,y = 2 ; 二次循环 ,y = 1;三次循环 y = 0;跳出当前循环；
   
7.     return x          #返回x的值为17;返回x = 2 ；返回x的值为 1；
   
8. print(gcd(53, 17))                打印当前的值，也就是返回的X值，为1；
   

复制代码

跳转到最佳答案楼层

heidern0612

1. 
   
2. def gcd(x, y):
   
3.     while y:     #y不为零时，开始循环;
   
4.         t = x % y  #一次循环，t =53 % 17 ,余数为2, t = 2;二次循环， t = 17/%2 = 1;三次循环，t = 2% 1 = 0;
   
5.         x = y        #一次循环，x = 17 ;二次循环，x = 2;三次循环 x = 1
   
6.         y = t        # 一次循环,y = 2 ; 二次循环 ,y = 1;三次循环 y = 0;跳出当前循环；
   
7.     return x          #返回x的值为17;返回x = 2 ；返回x的值为 1；
   
8. print(gcd(53, 17))                打印当前的值，也就是返回的X值，为1；
   

复制代码

heidern0612

看不明白的话，可以看我这个帖。

戳我前进

塔利班

谁大谁小没关系，下次就换顺序

Mountain_gs

如果 x<y
t = x %y =>t =x;
x = y      => x =y
y = t       => y =x
一次循环后x和y的值就会互换了。

xia3880417

其实代码看懂了。但是就是不懂为什么这个函数里不用区分x y的大小
你的例子是 x=53  y=17
t=53%17=2
t=17%2=1
几次循环下来
t=2%1=0
得到公约数为1

那么假如 x=17  y=53
那么  t=17%53 得到的是t=17
再次循环 t=53%17  就回到和x=53  y=17一样了。。