[数据结构][Python][经典题目]最大公约数

「爱情、让人受尽委屈。」 2022-01-10 16:39 239阅读 0赞

# 方案1 #

辗转相除法，又名欧几里得算法。  
定理：**两个正整数a和b（a>b)，他们的最大公约数等于a除以b 的余数c和b之间的最大公约数。**

def get_great_division(a,b):
        if a>b:
            big = a
            smal = b
        else:
            big = b
            smal = a
        if big%smal==0:
            return smal
        return get_great_division(big%smal,smal)
    if __name__ == '__main__':
        result = get_great_division(100,80)
        print(result)

# 方案2 #

更相减损法。  
定理：**两个正整数a和b（a>b)，他们的最大公约数等于a-b的差值c和较小数b的最大公约数**

def get_division(a,b):
        if a==b:
            return a
        if a>b:
            big = a
            smal = b
        else:
            big = b
            smal = a
        return get_division(big-smal,smal)

改进，gcd代表最大公约数  
**当a和b均为偶数的时候，gcd(a,b)=2*gcd(a/2,b/2)=2*gcd(a>>1,b>>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(b,a-b)，此时a-b必然是偶数，然后又可以进行位移运算**

def gcd(a,b):
        if a==b:
            return a
        if a&1==0 and b&1==0:
            return gcd(a>>1,b>>1)<<1
        elif a&1==0 and b&1 !=0:
            return gcd(a>>1,b)
        elif a&1!=0 and b&1==0:
            return gcd(a,b>>1)
        else:
            if a > b:
                big = a
                smal = b
            else:
                big = b
                smal = a
            return gcd(big-smal,smal)