起风了番茄 发表于 2021-12-23 00:07:44

求助一道欧几里算法

本帖最后由 起风了番茄 于 2021-12-23 00:11 编辑

def gcd(x, y):
    while y:
      t = x % y #这里x要小于y，为什么可以做取余运算？
      x = y
      y = t
      break

    return t
   
print(gcd(4, 6))
为何这里x要小于y，却可以做取余运算？

傻眼貓咪 发表于 2021-12-23 00:07:45

起风了番茄 发表于 2021-12-23 14:56
我自己答吧，余数 = 被除数 - 除数*商
以4%5为例
可以得出 余数mod = 4 - 5*int（4/5)


如图

傻眼貓咪 发表于 2021-12-23 00:11:58

为什么不能呢？3 除 7 得商 0 余 3 不是吗？

起风了番茄 发表于 2021-12-23 12:11:30

傻眼貓咪 发表于 2021-12-23 00:11
为什么不能呢？3 除 7 得商 0 余 3 不是吗？

3除7不是除不尽吗，我实在没搞懂

起风了番茄 发表于 2021-12-23 14:56:23

我自己答吧，余数 = 被除数 - 除数*商
以4%5为例
可以得出 余数mod = 4 - 5*int（4/5)
python中的上向下取值，
也就是说：mod = 4 - 5*0
mod = 4

傻眼貓咪 发表于 2021-12-23 23:06:51

起风了番茄 发表于 2021-12-23 12:11
3除7不是除不尽吗，我实在没搞懂

是啊，除不尽的部分就是余数啊，还是我理解错了？
页: [1]
查看完整版本: 求助一道欧几里算法