[已解决]求助python17讲的利用欧几里得算法求最大公约数

一支芦苇

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

    return x
   
print(gcd(4, 6))

这里为什么要while y ? 然后为什么是return x? 不太明白

最佳答案

月排行榜 / 总排行榜

自然水

2017-3-28 21:26:37

拿起纸和笔：

我们开始第一轮循环：
求 64 和 12 的最大公约数 ---

第一轮 ：

t =  64 % 12 = 4

将x替换为y的值 = 12

y =t = 4

这样下一轮 求最大公约数就是 gcd(x,y) = gcd(12,4)

第二轮

t = 12 % 4 = 0

将x替换为y的值 = 4

y =t = 0

当这轮t = 0 了，意味着被整除了。 那么最大公约数就是4了。

y 又被赋值为0

所以while = false 循环结束 ~~

跳转到最佳答案楼层

新手·ing

while y:表示进入一个循环，不然循环后面的条件只会实现一次
因为根据代码，x返回最大公因数

shuofxz

http://blog.csdn.net/yy13210520/article/details/6771591

具体过程你可以看下这篇文章

举个例子：
求48 18的最大公约数
48 / 18 = 2 …… 12          和 18  12的公约数是一样的
18 / 12 = 1 …… 6            和  12  6的公约数是一样的
这样的循环一直下去直到余数为零的时候，最后那个式子的除数就是最大公约数
即12 / 6 = 2 ……0

按这个过程你在理解一下代码

自然水

拿起纸和笔：

我们开始第一轮循环：
求 64 和 12 的最大公约数 ---

第一轮 ：

t =  64 % 12 = 4

将x替换为y的值 = 12

y =t = 4

这样下一轮 求最大公约数就是 gcd(x,y) = gcd(12,4)

第二轮

t = 12 % 4 = 0

将x替换为y的值 = 4

y =t = 0

当这轮t = 0 了，意味着被整除了。 那么最大公约数就是4了。

y 又被赋值为0

所以while = false 循环结束 ~~

一支芦苇

新手·ing 发表于 2017-3-28 21:11
while y:表示进入一个循环，不然循环后面的条件只会实现一次
因为根据代码，x返回最大公因数

好的，谢谢

新手·ing

一支芦苇 发表于 2017-3-28 21:56
好的，谢谢

等待最佳答案

一支芦苇

自然水 发表于 2017-3-28 21:26
拿起纸和笔：

我们开始第一轮循环：

写的很清楚，特别感谢，是不是当计算到4/0的时候，Python才意识到已经被整除了，所以结束了程序？

自然水

一支芦苇 发表于 2017-3-28 22:00
写的很清楚，特别感谢，是不是当计算到4/0的时候，Python才意识到已经被整除了，所以结束了程序？{:5_106 ...

不是。
是因为 y =0 了， 0 就是假  false

当第二轮循环结束，while语句开始判断是否继续循环： 但y在第二轮循环已经被赋值为0了。 所以条件不成立，结束循环。
（而这个0来源，是因为被整除了，获得了0.）
设计一个循环体条件的时候，去思考必然导致一种结果的因素，特征。 用这个作为条件，来控制语句。

一支芦苇

shuofxz 发表于 2017-3-28 21:14
具体过程你可以看下这篇文章

举个例子：

好的，谢谢

一支芦苇

自然水 发表于 2017-3-29 21:40
不是。
是因为 y =0 了， 0 就是假  false

嗯嗯，明白了。谢谢你

流月飞星

自然水 发表于 2017-3-28 21:26
拿起纸和笔：

我们开始第一轮循环：

屁哥

自然水 发表于 2017-3-28 21:26
拿起纸和笔：

我们开始第一轮循环：

双击 666