Python - 最大公约数算法

拼搏现实的明天。 2021-10-24 06:48 355阅读 0赞

# Python 3.6
    
    # 最大公约数，最大公因子
    # Greatest Common Divisor
    
    # 辗转相除法
    def gcd(num1: object, num2: object) -> object:
        print('num1={},num2={},r={}'.format( num1, num2, num1 % num2 ) )
        if num1 % num2 == 0:
            return num2
        return gcd(num2, num1 % num2)
    
    # 更相减损术（递归）
    def gcd2(num1, num2):
        bignum = num1 if num1 >= num2 else num2
        smallnum = num2 if num1 > num2 else num1
        difference = bignum-smallnum   # 差
        print('num1={},num2={},difference={}'.format(bignum, smallnum, difference))
        if smallnum == difference :
            return difference
        return gcd2(smallnum, difference);
    
    # 更相减损术 （循环）
    def gcd3(m, n):
        res=m-n
        while res != n:
            print('num1={},num2={},difference={}'.format(m, n, res))
            m = n if n >= res else res
            n = n if n <= res else res
            res = m - n
        return n
    
    print('-'*100)
    print(gcd2(9876,8756))
    print('-'*100)
    print(gcd2(9876, 8756))

PyCharm中，使用Shift+F9,得到如下结果：

Connected to pydev debugger (build 181.4892.64)  
num1=9876,num2=8756,r=1120  
num1=8756,num2=1120,r=916  
num1=1120,num2=916,r=204  
num1=916,num2=204,r=100  
num1=204,num2=100,r=4  
num1=100,num2=4,r=0  
4  
\----------------------------------------------------------------------------------------------------  
num1=9876,num2=8756,difference=1120  
num1=8756,num2=1120,difference=7636  
num1=7636,num2=1120,difference=6516  
num1=6516,num2=1120,difference=5396  
num1=5396,num2=1120,difference=4276  
num1=4276,num2=1120,difference=3156  
num1=3156,num2=1120,difference=2036  
num1=2036,num2=1120,difference=916  
num1=1120,num2=916,difference=204  
num1=916,num2=204,difference=712  
num1=712,num2=204,difference=508  
num1=508,num2=204,difference=304  
num1=304,num2=204,difference=100  
num1=204,num2=100,difference=104  
num1=104,num2=100,difference=4  
num1=100,num2=4,difference=96  
num1=96,num2=4,difference=92  
num1=92,num2=4,difference=88  
num1=88,num2=4,difference=84  
num1=84,num2=4,difference=80  
num1=80,num2=4,difference=76  
num1=76,num2=4,difference=72  
num1=72,num2=4,difference=68  
num1=68,num2=4,difference=64  
num1=64,num2=4,difference=60  
num1=60,num2=4,difference=56  
num1=56,num2=4,difference=52  
num1=52,num2=4,difference=48  
num1=48,num2=4,difference=44  
num1=44,num2=4,difference=40  
num1=40,num2=4,difference=36  
num1=36,num2=4,difference=32  
num1=32,num2=4,difference=28  
num1=28,num2=4,difference=24  
num1=24,num2=4,difference=20  
num1=20,num2=4,difference=16  
num1=16,num2=4,difference=12  
num1=12,num2=4,difference=8  
num1=8,num2=4,difference=4  
4  
\----------------------------------------------------------------------------------------------------  
num1=9876,num2=8756,difference=1120  
num1=8756,num2=1120,difference=7636  
num1=7636,num2=1120,difference=6516  
num1=6516,num2=1120,difference=5396  
num1=5396,num2=1120,difference=4276  
num1=4276,num2=1120,difference=3156  
num1=3156,num2=1120,difference=2036  
num1=2036,num2=1120,difference=916  
num1=1120,num2=916,difference=204  
num1=916,num2=204,difference=712  
num1=712,num2=204,difference=508  
num1=508,num2=204,difference=304  
num1=304,num2=204,difference=100  
num1=204,num2=100,difference=104  
num1=104,num2=100,difference=4  
num1=100,num2=4,difference=96  
num1=96,num2=4,difference=92  
num1=92,num2=4,difference=88  
num1=88,num2=4,difference=84  
num1=84,num2=4,difference=80  
num1=80,num2=4,difference=76  
num1=76,num2=4,difference=72  
num1=72,num2=4,difference=68  
num1=68,num2=4,difference=64  
num1=64,num2=4,difference=60  
num1=60,num2=4,difference=56  
num1=56,num2=4,difference=52  
num1=52,num2=4,difference=48  
num1=48,num2=4,difference=44  
num1=44,num2=4,difference=40  
num1=40,num2=4,difference=36  
num1=36,num2=4,difference=32  
num1=32,num2=4,difference=28  
num1=28,num2=4,difference=24  
num1=24,num2=4,difference=20  
num1=20,num2=4,difference=16  
num1=16,num2=4,difference=12  
num1=12,num2=4,difference=8  
num1=8,num2=4,difference=4  
4

Process finished with exit code 0

原理：[https://zhidao.baidu.com/question/177881849738799124.html][https_zhidao.baidu.com_question_177881849738799124.html]

转载于:https://www.cnblogs.com/wangqiideal/p/9539762.html

[https_zhidao.baidu.com_question_177881849738799124.html]: https://zhidao.baidu.com/question/177881849738799124.html