[已解决]零基础入门学习python第17讲作业，动动手第一题

春卷啊

求问求x,y的最大公约数，答案中为什么是return x 而不是返回y呢？
def gcd(x, y):
    while y:
        t = x % y
        x = y
        y = t

    return x
   
print(gcd(4, 6))

最佳答案

月排行榜 / 总排行榜

Der_kokon

2018-4-23 21:11:06

实际上欧几里德算法求最大公约数是迭代算法，辗转相除。
比如x = 6, y = 4,求6和4的最大公约数，为了方便，我们始终假定x>y,如果不满足这个条件就调换x与y的值，
接下来，过程如下：
                 x          y         t                              x           y         
step1:        6          4         2        --------〉         4           2
step2:        4          2         0        --------〉         2           0

此时你想一下，如果返回x，则6和4的最大公约数就是2，如果返回y，即6和4的最大公约数为0,
因为只有y=0的时候结束循环，实际上，如果返回y，任何两个数的最大公约数都是0，这就把蛋给扯着了，对吧。
后面讲到递归的时候，你就能看到小甲鱼的另一种解法：
def gcb(x, y):
     if x % y:
          gcb(y, x%y)
      return x
a = gcb(6, 4)
print('6和4的最大公约数是：'，a)       

跳转到最佳答案楼层

BngThea

逻辑上决定的
你可以试试return y看看结果

Der_kokon

实际上欧几里德算法求最大公约数是迭代算法，辗转相除。
比如x = 6, y = 4,求6和4的最大公约数，为了方便，我们始终假定x>y,如果不满足这个条件就调换x与y的值，
接下来，过程如下：
                 x          y         t                              x           y         
step1:        6          4         2        --------〉         4           2
step2:        4          2         0        --------〉         2           0

此时你想一下，如果返回x，则6和4的最大公约数就是2，如果返回y，即6和4的最大公约数为0,
因为只有y=0的时候结束循环，实际上，如果返回y，任何两个数的最大公约数都是0，这就把蛋给扯着了，对吧。
后面讲到递归的时候，你就能看到小甲鱼的另一种解法：
def gcb(x, y):
     if x % y:
          gcb(y, x%y)
      return x
a = gcb(6, 4)
print('6和4的最大公约数是：'，a)       

感觉自己萌萌哒

因为最后一次计算之后，y肯定等于0了，不然while会继续循环吧。
而X在最后一次计算之后,X=Y，即X替代成Y变成被除数了，也就是公约数

thexiosi

Der_kokon 发表于 2018-4-23 21:11
实际上欧几里德算法求最大公约数是迭代算法，辗转相除。
比如x = 6, y = 4,求6和4的最大公约数，为了方便 ...

解释的很好 ：）

有一点小瑕疵，另一种解法的代码错误了，会陷入无限递归，修改如下哈

def gcb(x, y):
    if  x % y:
        gcb(y,x%y)
    return x

thexiosi

thexiosi 发表于 2018-4-24 09:38
解释的很好 ：）

有一点小瑕疵，另一种解法的代码错误了，会陷入无限递归，修改如下哈

晕了，我也写错了，修改如下

def gcb(x, y):
    if  x % y == 0:
        return y
    return gcb(y,x%y)

machinism

你可以了解一下辗转相除法求最大公约数，你大概就了解了

Der_kokon

thexiosi 发表于 2018-4-24 09:38
解释的很好 ：）

有一点小瑕疵，另一种解法的代码错误了，会陷入无限递归，修改如下哈

对，谢谢指正。

thexiosi

Der_kokon 发表于 2018-4-24 15:17
对，谢谢指正。

没事 ：）

春卷啊

BngThea 发表于 2018-4-23 20:43
逻辑上决定的
你可以试试return y看看结果

非常感谢

春卷啊

Der_kokon 发表于 2018-4-23 21:11
实际上欧几里德算法求最大公约数是迭代算法，辗转相除。
比如x = 6, y = 4,求6和4的最大公约数，为了方便 ...

非常感谢，看明白了

春卷啊

感觉自己萌萌哒 发表于 2018-4-23 22:18
因为最后一次计算之后，y肯定等于0了，不然while会继续循环吧。
而X在最后一次计算之后,X=Y，即X替代成Y变 ...

非常感谢