欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

四种方法求最大公约数(Python)

程序员文章站 2023-12-21 20:12:34
...

一、最大公约数
二、解题思路
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转化成二进制,再进行与运算,就会明白。

相关标签: 笔面试试题

上一篇:

下一篇: