[已解决]每天一个小问题

smartsy

题目为利用欧几里得算法求最大公约数
def gcd(x, y):
    while y:
        t = x % y
        x = y
        y = t

    return x
   
print(gcd(4, 6))


此代码从第二行开始就已经不懂了，为什么要用y进入循环？余数t为什么要赋值给y？y为什么要赋值给x？为什么最后返回x以后就能保证求得最大公约数？内在逻辑是怎么运行的？
我查过欧几里得算法求最大公约数，是2个整数中较小的那个数除以这2个整数相除的余数即为最大公约数，但是这个代码我完全找不到内在的逻辑，求解答

最佳答案

月排行榜 / 总排行榜

昨非

2021-4-23 23:28:07

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

跳转到最佳答案楼层

昨非

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

wp231957

辗转相除法，搜一下
都不用搜索引擎的吗

罗巴乔

辗转相除法，学到了

qq1151985918

你得知道欧几里得算法的原理啊