第022讲，动动手第二题，求最大公约数

薄荷的琦姑娘

首先看到这个题的时候我是崩溃的，因为我查了欧几里得算法，定理是：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
不得解，完全没明白。
后来瞎倒腾还是没出结果。实在没办法，看了小甲鱼老师的答案，然后再改改自己的程序，依旧不得解。

1. def gcd(x,y):
   
2.     if x == 0:
   
3.         return 0
   
4.     elif y == 0:
   
5.         return 0
   
6.     else:
   
7.         if x > y:
   
8.             return gcd(y,x%y)
   
9.         else:
   
10.             return gcd(x,y%x)
    
11.         
    
12. 
    
13. temp = int(input('pls input x:'))
    
14. temp1 = int(input('pls input y:'))
    
15. result = gcd(temp,temp1)
    
16. print(' gcd is %d'%result)
    

复制代码

如果我  x = 4, y = 6 ,得的结果始终是 0 ， 为什么呢？ 而且如果求两个数的最大公约数，一个数为0 的话，最大公约数不是应该等于 0 吗，求大神讲解。

yongxi

def gcd(x,y):
    if x == 0:
        return 0
    elif y == 0:
        return x
    else:
        if x > y:
            return gcd(y,x%y)
        else:
            return gcd(x,y%x)
        

temp = int(input('pls input x:'))
temp1 = int(input('pls input y:'))
result = gcd(temp,temp1)
print(' gcd is %d'%result)

0是不能被作为除数的！！ 这是数学里面的最基本定义
所以，用递归寻找最大公约数， 其递归的停止条件就是除数等于0(上一次递归中已经被整除了，除数就是最大公约数)
因此 ，修改如下
    elif y == 0:
        return 0
return 0  改成 return x  即可！

薄荷的琦姑娘

yongxi 发表于 2017-5-18 17:14
def gcd(x,y):
    if x == 0:
        return 0

是的呢，谢谢你。可是我在这里并没想把任何一个为0 的数作为除数，只是说，如果某个为 0 ，就直接返回 0 ，毕竟一个正常数和 0 求余，那结果当然是返回 0 呀。为啥第二个if 改为return x 就好了。不解。。。

yongxi

薄荷的琦姑娘 发表于 2017-5-18 17:55
是的呢，谢谢你。可是我在这里并没想把任何一个为0 的数作为除数，只是说，如果某个为 0 ，就直接返回 0  ...

用递归寻找最大公约数， 其递归的停止条件就是除数等于0(上一次递归中已经被整除了，除数就是最大公约数)
求 x 与 y 的最大公约数：
x    y    x%y      如果x%y不等于0  那么把y作被为除数 x%y作为除数 再次求余数  直到x%y等于0 就是被整除了。那么最大公约数就是除数  
这一段文字的意思就是翻译以下代码：
elif y == 0:
        return x
    else:
        if x > y:
            return gcd(y,x%y)
        else:
            return gcd(x,y%x)
既然 函数gcd的形参y==0了。  那么久应该停止递归， 返回最大公约数的值(即是X)

如果还不明白，请楼主百度辗转相除算法的原理
原理弄懂了，你就明白了

yongxi

还有 。 递归函数 很重要的一点就是 递归的停止条件~！！！！
建议楼主再看一次教学视频