欧几里得算法实现

it2022-05-06  9

欧几里得算法用于计算两个正整数的最大公约数。原理就是a和b的公约数(a>b)等于b和 mod(a,b)的公约数(mod(a,b)!= 0),也等于mod(a,b)和mod(b,mod(a,b))的公约数。

假如mod(a,b)== 0,那么b就是最大公约数。当然所有b的约数也是a,b的约数。

实现1:

这是非递归实现方式。首先确保a > b,如果a % b != 0,那么就计算b和mod(a , b)的余数,直到mod(a, b) == 0为止,这时b就是最大公约数。

def gcd(a, b): if a < b: tmp = b b = a a = tmp while(a % b != 0): r = a % b a = b b = r return b print(gcd(640, 1680))

实现2:

因为所有的gcd2函数的返回值都是为了求取同一个最大公约数,所以它们的返回值是一致的。结果都是80.

def gcd2(a, b): if a < b: tmp = b b = a a = tmp if a % b != 0: return gcd2(b, a % b) else: return b print(gcd2(640, 1680))

 


最新回复(0)