课程
/后端开发
/Python
/python进阶
def gcd(a, b): if b == 0: return a return gcd(b, a % b)
2018-12-04
源自：python进阶 6-5
正在回答
欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
百度一下辗转相除法
因为一个数最大的因数是其本身，即 x / 1 = x，再次就是它的一半。
所以通过反复比较a，b两个数，当a除以b余数为0时，即找到了它们之间的最大公约数。
比如：gcd(25,15)=>gcd(15,10)=>gcd(10,5)=>gcd(5,0)，返回的a值5就是结果。
再如：gcd(15,25)=>gcd(25,15)=>gcd(15,10)=>gcd(10,5)=>gcd(5,0)
慕侠8496208
举报
学习函数式、模块和面向对象编程，掌握Python高级程序设计
