[已解决]第17讲动动手1 有疑惑（忽略上一个）

AquamanZ

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

    return x
   
print(gcd(4, 6))

欧几里德算法：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。

那么t是余数，我们让x ＝ y（x变为除数）， y ＝ t（y变为余数）之后，再进行下一轮运算的时候 x ％ y 就变成了：除数除以余数了，这是有悖于原理的啊？

最佳答案

月排行榜 / 总排行榜

thexiosi

2018-5-7 16:05:54

hi 楼主应该是对整个运算过程有疑惑，举个栗子 gcd(4,6)，这样是不是清楚了一些。后续遇到类似问题，建议 通过具体的例子、结合算法原理进行细分理解

第一轮：y = 6  为真，进入while循环，t = 4 % 6 得到 t =4 ，x = 6  y =4   # x ＝ y， y ＝ t 的意义就是让 '较大数 求余 较小数'  或  ' 较小数 求余 余数 ' 持续进行，直到最终余数为0；余数为0 那一轮的较小数就是最大公约数
第二轮：y = 4  为真，继续while循环，t = 6 % 4 得到 t = 2 ，x = 4, y = 2
第三轮：y = 2  为真，继续while循环，t = 4 % 2 得到 t = 0 ，x = 2, y = 0
第四轮：y = 0  为假，退出while循环，返回x的值 2

跳转到最佳答案楼层

塔利班

只有求余，没见除数

ba21

除数除以余数了，这是有悖于原理的啊？

请问怎么个悖于原理 法？  不管你是 除数  余数 最终还只是 个数字吧。
只是 个数字 可以理解不？ 看你上的文字也解释的很清楚了

AquamanZ

塔利班 发表于 2018-5-6 15:47
只有求余，没见除数

那么x ＝ y， y ＝ t 的意义是什么呢

thexiosi

hi 楼主应该是对整个运算过程有疑惑，举个栗子 gcd(4,6)，这样是不是清楚了一些。后续遇到类似问题，建议 通过具体的例子、结合算法原理进行细分理解

第一轮：y = 6  为真，进入while循环，t = 4 % 6 得到 t =4 ，x = 6  y =4   # x ＝ y， y ＝ t 的意义就是让 '较大数 求余 较小数'  或  ' 较小数 求余 余数 ' 持续进行，直到最终余数为0；余数为0 那一轮的较小数就是最大公约数
第二轮：y = 4  为真，继续while循环，t = 6 % 4 得到 t = 2 ，x = 4, y = 2
第三轮：y = 2  为真，继续while循环，t = 4 % 2 得到 t = 0 ，x = 2, y = 0
第四轮：y = 0  为假，退出while循环，返回x的值 2

AquamanZ

thexiosi 发表于 2018-5-7 16:05
hi 楼主应该是对整个运算过程有疑惑，举个栗子 gcd(4,6)，这样是不是清楚了一些。后续遇到类似问题，建议  ...

我又提问啦求您解答啊！