枫枫duck 发表于 2020-4-9 10:36:09

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

本帖最后由 枫枫duck 于 2020-4-9 10:38 编辑

def gcd(x,y):
    big = x if x>y else y
    small = y if x>y else x
    while 1:
      num = big%small
      if num == 0:
            return small
            break
      else:
            big = small
            small = big%small
      
以上是我的编码，它会报错
gcd(4,6)
Traceback (most recent call last):
File "<pyshell#0>", line 1, in <module>
    gcd(4,6)
File "C:\Users\15860\Desktop\python学习\lesson17函数\欧几里得.py", line 5, in gcd
    num = big%small
ZeroDivisionError: integer division or modulo by zero
是说除数不能为0吗，为什么错了呢

liuzhengyuan 发表于 2020-4-9 10:38:51

本帖最后由 liuzhengyuan 于 2020-4-9 10:51 编辑

这个不对。。。
你这个

else:
            big = small
            small = big%small

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

qiuyouzhi 发表于 2020-4-9 10:39:56

本帖最后由 qiuyouzhi 于 2020-4-9 10:41 编辑

def gcd(x,y):
    big = x if x>y else y
    small = y if x>y else x
    while 1:
      num = big % small
      if num == 0:
            return small
      else:
            small = big%small

print(gcd(4,6))
return了之后，程序就直接结束了，不用break

枫枫duck 发表于 2020-4-9 10:41:13

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 发表于 2020-4-9 10:42:08

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

你这个


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

枫枫duck 发表于 2020-4-9 10:42:54

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

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

枫枫duck 发表于 2020-4-9 10:44:56

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

你这个


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

qiuyouzhi 发表于 2020-4-9 10:45:35

枫枫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 发表于 2020-4-9 10:47:39

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


我把它修改了，应该没问题了！让small=num就好了
def gcd(x,y):
    big = x if x>y else y
    small = y if x>y else x
    while 1:
      num = big%small
      if num == 0:
            return small            
      else:
            big = small
            small = num
      
页: [1]
查看完整版本: 利用欧几里得算法（脑补链接）求最大公约数