[已解决]使用递归编写一个函数，利用欧几里得算法求最大公约数，例如 gcd(x, y) 返回值为参...

无功

def gcd(x, y):
    if y:
        return gcd(y, x%y)
    else:
        return x
   
print(gcd(4, 6))

求解释 ，谢谢谢谢谢谢

最佳答案

月排行榜 / 总排行榜

ouyunfu

2020-7-30 20:57:39

这里计算原理依赖于下面的定理：
两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

1. def gcd(x, y):
   
2.     if y: # y不等于0，执行下一语句，否则执行else
   
3.         print('gcd({},{})'.format(y,x%y)) #这样打印希望有助于理解
   
4.         return gcd(y, x%y) #这里是一个函数迭代，即x=y, y=x%y, 直到y=0, 返回x
   
5.     else:
   
6.         return x
   
7.    
   
8. print(gcd(4, 6))

复制代码

跳转到最佳答案楼层

zltzlt

请见：https://fishc.com.cn/forum.php?m ... 67183&ctid=1730

ouyunfu

这里计算原理依赖于下面的定理：
两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

1. def gcd(x, y):
   
2.     if y: # y不等于0，执行下一语句，否则执行else
   
3.         print('gcd({},{})'.format(y,x%y)) #这样打印希望有助于理解
   
4.         return gcd(y, x%y) #这里是一个函数迭代，即x=y, y=x%y, 直到y=0, 返回x
   
5.     else:
   
6.         return x
   
7.    
   
8. print(gcd(4, 6))

复制代码