辗转相除法+更相减损法求最大公约数

时间：2021-04-12 00:29:55

怎么求两个数的最大公约数呢？
简单的想法就是直接暴力枚举，试出最大公约数

暴力枚举

#暴力枚举
def GCD(numberA,numberB):
    gcd=1
    for i in range(2,max(numberA,numberB)+1):
        if numberA%i == 0 and numberB%i == 0:
            gcd=i
    return gcd

这显然不是一个好的算法，那么应该怎么优化呢？

辗转相除法

公元前300年前就有了这类问题的解法：辗转相除法， 又名欧几里得算法（Euclidean algorithm），目的是求出两个正整数的最大公约数。它是已知最古老的算法。

这条算法基于一个定理：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25，25除以10商2余5,那么10和25的最大公约数，等同于10和5的最大公约数。

#辗转相除法——欧几里得算法
''' 两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。 比如10和25，25除以10商2余5,那么10和25的最大公约数，等同于10和5的最大公约数。 缺点：做a%b运算的时候效率比较低 '''      
def GCD_Euclidean(numberA,numberB):
    gcd=1
    if numberA>numberB:
        return getresult(numberA,numberB)
    else :
        return getresult(numberB,numberA)
    return gcd
def getresult(big,small):
    if big%small is 0:
        return small
    else :
        return getresult(small,big%small)

更相减损法

但是在取模运算的时候效率很低，有没有什么办法优化呢？

中国古代的《九章算术》中就有了相应的办法：更相减损术，也是一种求最大公约数的算法。

它的原理更加简单：两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。比如10和25，25减去10的差是15,那么10和25的最大公约数，等同于10和15的最大公约数

#更相减损术， 出自于中国古代的《九章算术》，也是一种求最大公约数的算法。
''' 两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。 比如10和25，25减去10的差是15,那么10和25的最大公约数，等同于10和15的最大公约数。 缺点：如果两数相差很远，如10000 和 1就需要迭代很多次 '''
def GCD_jiuzhang(numberA,numberB):
    gcd=1
    if numberA>numberB:
        return get_jiuzhang(numberA,numberB)
    else :
        return get_jiuzhang(numberB,numberA)
    return gcd
def get_jiuzhang(numberA,numberB):
    if numberA is numberB:
        return numberA
    if numberA>numberB:
        return GCD_jiuzhang(numberB,numberA-numberB)
    else:
        return GCD_jiuzhang(numberB,numberB-numberA)

但是计算1000000和1的时候需要递归很多次，有没有什么办法优化呢？

此时应该将前面提到的，辗转相除法和更相减损术结合起来，在更相减损术的基础上用上移位运算

辗转相除法+更相减损法

众所周知，移位运算的性能非常快。对于给定的正整数a和b，不难得到如下的结论。
其中gcb(a,b)的意思是a,b的最大公约数函数：

  • 当a和b均为偶数，gcb(a,b) = 2*gcb(a/2, b/2) = 2*gcb(a>>1, b>>1)

  • 当a为偶数，b为奇数，gcb(a,b) = gcb(a/2, b) = gcb(a>>1, b) 偶数和奇数的最大公约数==奇数和偶数的一半的最大公约数

  • 当a为奇数，b为偶数，gcb(a,b) = gcb(a, b/2) = gcb(a, b>>1)

  • 当a和b均为奇数，利用更相减损术运算一次，gcb(a,b) = gcb(b, a-b)， 此时a-b必然是偶数，又可以继续进行移位运算。

def GCD_Ecu_jiuzhang(numberA,numberB):
    gcd=1
    if numberA>numberB:
        return get_Ecu_jiuzhang(numberA,numberB)
    else :
        return get_Ecu_jiuzhang(numberB,numberA)
    return gcd
def get_Ecu_jiuzhang(numberA,numberB):
    if numberA is numberB:
        return numberA
    if numberA<numberB:
        return get_Ecu_jiuzhang(numberB,numberA)#保证每次都是前一个数大于后一个数
    else:
        #都是偶数的情况
        if numberA%2 == numberB%2 ==0:
            return get_Ecu_jiuzhang(numberA>>1,numberB>>1)<<1
        #A是偶数，B是奇数
        elif numberA%2==0 and numberB%2!=0:
            return get_Ecu_jiuzhang(numberA>>1,numberB)
        #A是奇数，B是偶数
        elif  numberB%2==0 and numberA%2!=0:
            return get_Ecu_jiuzhang(numberA,numberB>>1)
        #都是奇数
        else:
            return get_Ecu_jiuzhang(numberA-numberB,numberB)

参考
https://juejin.im/post/5a217bac51882531926e8656?utm_source=gold_browser_extension

标签：

相关文章