四种方法求最大公约数(Python)
一、最大公约数
二、解题思路
1、暴力枚举法
2、辗转相除法
3、更相减损术
4、更相减损术与移位相结合
一、最大公约数
题目:写一段代码,求出两个整数的最大公约数,要尽量优化算法性能。
在这里补充一下:最大公约数和最小公倍数与原数据a,b存在运算关系,假设a,b的最大公约数是x,最小公倍数是y,则有ab=xy,所以最大公约数和最小公倍数知道一个就可以求出另一个。
二、解题思路
1、暴力枚举法
从较小整数的一半开始,试图找到一个合适的整数i,看这个数能否被a,b同时整除。
它的时间复杂度为O(min(a,b))
缺点:暴力枚举法效率比较低,当我传入的整数是10000和10001时,这种方法要比较10000/2-1=4999次。
暴力枚举法的代码实现:
def get_greatest_common_divisor(a,b):
big=max(a,b)
small=min(a,b)
if big%small==0:
return small
for i in range(small//2,1,-1):
if small%i==0 and big%i==0:
return i
return 1
print(get_greatest_common_divisor(26,13))
2、辗转相除法
辗转相除法,又名欧几里得算法,该算法的目的是求出两个数的最大公约数。
它源于一个定理:
两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。(即:每次都是求余数和较小数之间最大公约数,直到两个数可以整除或者其中一个数减小到1为止。)
辗转相除法的时间复杂度不太好计算,可以近似为O(log(max(a,b))),但是取模运算的性能比较差。
缺点:辗转相除法中,当两个整数比较大时,做a%b取模运算的性能会比较差。
辗转相除法的代码实现
def get_greatest_common_divisor_V2(a,b):
big=max(a,b)
small=min(a,b)
if big%small==0:
return small
return get_greatest_common_divisor_V2(big%small,small)
print(get_greatest_common_divisor_V2(26,13))
3、更相减损术
更相减损术也源于一个定理:
两个正整数a和b(a>b),它们的最大公约数等于a-b的差值c和较小数b之间的最大公约数。(即:每次都是求差值和较小数之间最大公约数,直到两个数相等为止,最大公约数就是最终相等的这两个数的值。)
更相减损术避免了取模运算,但是算法性能不稳定,最坏时间复杂度为O(max(a,b))
缺点:更相减损术是不稳定的算法,当两数相差悬殊时,如计算10000和1的最大公约数,就要递归9999次。运算次数太多,
更相减损术代码实现:
def get_greatest_common_divisor_V3(a,b):
if a==b:
return a
big = max(a, b)
small = min(a, b)
return get_greatest_common_divisor_V3(big-small,small)
print(get_greatest_common_divisor_V3(26,13))
4、更相减损术与移位相结合
根据前面介绍,我们发现,有没有一种方法既可以避免大整数取模,又能尽可能的减少运算次数呢?
接下来介绍一种最优的方法:把辗转相除法和更相减损术结合起来,在更相减损术的基础上使用移位运算。(移位运算差不多是辗转相除法的运用,不过是遇到偶数时,每次向右移一位,对于整数十进制来说,相当于除以2)
移位运算的性能非常好。
接下来介绍具体方法:
求最大公约数的方法简写为gcd.
当a、b均为偶数时,gcd(a,b)=2gcd(a/2,b/2)=2gcd(a>>1,b>>1)=gcd(a>>1,b>>1)<<1
当a为偶数b为奇数时,gcd(a,b)=gcd(a/2,b)=gcd(a>>1,b)
当a为奇数b为偶数时,gcd(a,b)=gcd(a,b/2)=gcd(a,b>>1)
当a、b均为奇数时,先利用更相减损术减一次,gcd(a,b)=gcd(a-b,b),此时a-b必为偶数,然后又可以继续进行移位运算。
这种方法在两数都比较小时,看不出来计算的优势;当两数越大时,计算次数的减少就会越明显。这种方法既避免大整数取模,又减少了运算次数,而且算法性能稳定,时间复杂度为O(log(max(a,b)))
代码实现
def get_greatest_common_divisor_V4(a,b):
if a==b:
return a
if (a&1)==0 and (b&1)==0:
return get_greatest_common_divisor_V4(a>>1,b>>1)<<1
elif (a & 1) == 0 and (b & 1) != 0:
return get_greatest_common_divisor_V4(a>>1,b)
elif (a & 1) != 0 and (b & 1) == 0:
return get_greatest_common_divisor_V4(a,b>>1)
else:
big=max(a,b)
small=min(a,b)
return get_greatest_common_divisor_V4(big-small,small)
print(get_greatest_common_divisor_V4(26,13))
在上述代码中,判断奇偶性的方式是让整数和1做与运算,如果(a&1)==0,则说明a是偶数,反之a是奇数。具体原因可以把a转化成二进制,再进行与运算,就会明白。