[已解决]关于求最大公约数

tuple小白

def gcd(a, b):
    while a != 0:
        a, b = b % a, a
    return b

这一句代码看不明白a,b =b%a,a

小白求教

最佳答案

月排行榜 / 总排行榜

zero月蚀的假面

2018-1-16 22:27:30

首先你要明白它的原理,比如a=2322，b=462：
a=2322，b=462 ，a%b=12
a=462 , b=12 ,a%b= 6
a=12 , b=6 ,a%b = 0
可以看出第一次的除数（b） = 第二次的被除数（a），而第一次的余数（a%b） = 第二次的除数（b）
所以我们只需要求到每次的除数（b）和余数（a%b）即可
当最后除数（b）=（a%b）=0时停止，而此时的a就是我们要求的最大公约数（a）=（b）=6

1. def gcd(a, b):   
   
2. while b:        
   
3.     a, b = b, a%b   
   
4. return a

复制代码

a,b = b,a%b就是在while循环里面一直赋值求余数的过程，当b=0时才结束
即a = b，b = a%b

跳转到最佳答案楼层

zero月蚀的假面

首先你要明白它的原理,比如a=2322，b=462：
a=2322，b=462 ，a%b=12
a=462 , b=12 ,a%b= 6
a=12 , b=6 ,a%b = 0
可以看出第一次的除数（b） = 第二次的被除数（a），而第一次的余数（a%b） = 第二次的除数（b）
所以我们只需要求到每次的除数（b）和余数（a%b）即可
当最后除数（b）=（a%b）=0时停止，而此时的a就是我们要求的最大公约数（a）=（b）=6

1. def gcd(a, b):   
   
2. while b:        
   
3.     a, b = b, a%b   
   
4. return a

复制代码

a,b = b,a%b就是在while循环里面一直赋值求余数的过程，当b=0时才结束
即a = b，b = a%b

orino

相当于是两句
a=b%a
b=a
然后返回 b

orino

这里用了辗转相除法， 又名欧几里德算法，循环来求得GCD,关于算法，详见https://baike.baidu.com/item/%E8%BE%97%E8%BD%AC%E7%9B%B8%E9%99%A4%E6%B3%95

鱼油127327

你把代码改成这样就理解了
def gcd(a, b):
    while a != 0:
        temp=a  #暂存上一次除的除数
        a = b % a #存上一次除的余数
        b=temp
    print(b)