[已解决]利用欧几里得算法（脑补链接）求最大公约数

枫枫duck

1. def gcd(x,y):
   
2.     big = x if x>y else y
   
3.     small = y if x>y else x
   
4.     while 1:
   
5.         num = big%small
   
6.         if num == 0:
   
7.             return small
   
8.             break
   
9.         else:
   
10.             big = small
    
11.             small = big%small [code]
    
12.       
    
13. 以上是我的编码，它会报错
    
14. [code]gcd(4,6)
    
15. Traceback (most recent call last):
    
16.   File "<pyshell#0>", line 1, in <module>
    
17.     gcd(4,6)
    
18.   File "C:\Users\15860\Desktop\python学习\lesson17函数\欧几里得.py", line 5, in gcd
    
19.     num = big%small
    
20. ZeroDivisionError: integer division or modulo by zero

复制代码

是说除数不能为0吗，为什么错了呢

最佳答案

月排行榜 / 总排行榜

liuzhengyuan

2020-4-9 10:38:51

这个不对。。。
你这个

1. else:
   
2.             big = small
   
3.             small = big%small

复制代码

想一想，
你先把big赋值small
这样big和small就一样了
两个一样的数相除余数就是0

跳转到最佳答案楼层

liuzhengyuan

这个不对。。。
你这个

1. else:
   
2.             big = small
   
3.             small = big%small

复制代码

想一想，
你先把big赋值small
这样big和small就一样了
两个一样的数相除余数就是0

qiuyouzhi

1. def gcd(x,y):
   
2.     big = x if x>y else y
   
3.     small = y if x>y else x
   
4.     while 1:
   
5.         num = big % small
   
6.         if num == 0:
   
7.             return small
   
8.         else:
   
9.             small = big%small
   
10. 
    
11. print(gcd(4,6))

复制代码

return了之后，程序就直接结束了，不用break

枫枫duck

liuzhengyuan 发表于 2020-4-9 10:38
这个不对。。。

你这个

我这里是想把small的值赋给big来达到
"""1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公约数为1"""
这种效果

qiuyouzhi

liuzhengyuan 发表于 2020-4-9 10:38
这个不对。。。

你这个

为什么要big == small呢？
直接删掉不行？

枫枫duck

qiuyouzhi 发表于 2020-4-9 10:39
return了之后，程序就直接结束了，不用break

谢谢提醒，但不影响程序是错的呀...

枫枫duck

liuzhengyuan 发表于 2020-4-9 10:38
这个不对。。。

你这个

我知道你的意思了，big已经改变了

qiuyouzhi

枫枫duck 发表于 2020-4-9 10:41
我这里是想把small的值赋给big来达到
"""1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)

假设按你的来：
1997 / 615 余 152
然后big = small，也就是把1997改成615
这时就变成615/615了

枫枫duck

qiuyouzhi 发表于 2020-4-9 10:45
假设按你的来：
1997 / 615 余 152
然后big = small，也就是把1997改成615

我把它修改了，应该没问题了！让small=num就好了

1. def gcd(x,y):
   
2.     big = x if x>y else y
   
3.     small = y if x>y else x
   
4.     while 1:
   
5.         num = big%small
   
6.         if num == 0:
   
7.             return small            
   
8.         else:
   
9.             big = small
   
10.             small = num
    
11.         
    

复制代码