[已解决]【第22讲课后题】欧几里得算法求最大公约数的输入顺序

不自在的风

1. 使用递归编写一个函数，利用欧几里得算法求最大公约数，例如 gcd(x, y) 返回值为参数 x 和参数 y 的最大公约数。
def gcd(x, y):
    if y:
        return gcd(y, x%y)
    else:
        return x
   
print(gcd(4, 6))
复制代码

以上是答案

我自己写的是这样的:

def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y, y % x)
   
gcd(104,260)
Out[100]: 52
gcd(260,104)
Out[101]: 104

也就是说，答案以及我写的，都没有考虑xy的大小顺序问题
我试了一下，如果写在函数里交换大小，会出问题
题目是不是得有个默认限定，x > y  ？？

最佳答案

月排行榜 / 总排行榜

2012277033

2019-5-17 17:11:28

这个之前有讲过的
如果小的去取余大的，那结果还是他本身,然后调换位置，小的和大的刚好反过来，举个例子
执行
gcd(12,18)
|
gcd(18,12%18) == gcd(18,12)
这样又正常了。

跳转到最佳答案楼层

jackz007

     欧几里得算法非常科学，在输入参数的时候，可以随意安排顺序，不需要一定 x > y。

     gcd(x , y) 如果 x < y，则 x % y = x，gcd(y ,  x % y) 实际上不就是 gcd(y , x) 吗？

wp231957

def gcd(x, y):
    if y:
        return gcd(y, x%y)
    else:
        return x
   
print(gcd(4, 6))
这个代码 我测试，无论大小谁再前面 都可以啊

2012277033

这个之前有讲过的
如果小的去取余大的，那结果还是他本身,然后调换位置，小的和大的刚好反过来，举个例子
执行
gcd(12,18)
|
gcd(18,12%18) == gcd(18,12)
这样又正常了。