smartsy 发表于 2021-4-23 23:25:49

每天一个小问题

题目为利用欧几里得算法求最大公约数
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；

wp231957 发表于 2021-4-24 07:12:33

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

罗巴乔 发表于 2021-4-24 07:26:59

辗转相除法，学到了

qq1151985918 发表于 2021-4-24 08:13:43

你得知道欧几里得算法的原理啊
页: [1]
查看完整版本: 每天一个小问题