编程的精髓来自算法，算法的精髓来自数学。编程只是数学问题的代码。《----润生》先问你一道小学题：“如何求两个整数的最大公约数？”看过很多算法题，发现有的不是在数据结构和算法大纲里，而是在高中数学里出源。在高中数学第三必修课中，有一个非常重要的知识点，叫做“滚分法，多相减法”。欧几里得算法，又称欧氏算法，是??一种求两个正整数的最大公因数的算法。它是已知最古老的算法，可追溯到公元前300年之前。古代有一位著名的数学家，名叫“刘徽”。更相减法记载于中国数学家刘辉的专着《九章算术》中。滚动除法是一种寻找最大公约数的算法。给定两个数，我们可以把它变成一对(a,b)。滚动除法是根据以下原则：“两个整数的最大公约数等于较小数的最大公约数与两个数相除的余数。”求出最大公约数a和b，用ab中较小的数除另一个数。这时候，就会有余数。当余数为0时，较小的数为最大公约数。如果余数不为0，则用这个余数代替较大的数，以此类推，直到计算出最大公约数。比如下面我用滚滚除法求100和24的最大公约数，显然最大公约数是25。100=24*4+424=4*6+0。很明显，4和6中较小的那个数4就是100和24的最大公约数，接下来用滚动除法求55和120的最大公约数。显然，最大公约数是5。55=120*0+55120=55*2+1055=10*5+5显然，10和5中，那个较小的数5是55和120的最大公约数。算法流程图（摘自百度百科全书）由此得到。设两个数为m和n，不需要判断这两个数哪个最大。求两个数m和n的最大公约数的步骤是：m除以n，m%n=r(r>=0)。如果r=0，则为min(m,n)。如果r≠0，则将n除以r，依此类推，直到r=0。接下来，我们将使用滚动和划分的方法来编码。defgcd(a,b):#如果b为0，退出循环whileb:#循环赋值a,b=b,a%breturnaprint(gcd(100,25))#25滚分法本质上是递归代码，将两个大数的公约数gcd(a,b)转化为较小数的最大公约数gcd(b,a%b)和两个数相除的余数，直到b为0，然后返回a作为获得的最大公约数gcd(gcd(a,b),0)。所以你可以得到：gcd(a,b)=gcd(b,a%b)=gcd(gcd(a,b),0)defgcd(a,b):returngcd(b,a%b)ifb!=0elseaprint(gcd(55,120))#5下面将Python代码转换为Java代码/***@authorRunsen*@date2020/12/913:18*/publicclassGcd{publicstaticvoidmain(String[]args){intgcd=gcd(91,49);System.out.println(gcd);}privatestaticintgcd(inta,intb){while(b!=0){inttemp=a%b;a=b;b=temp;}returna;}}下面转换Python代码到JavaScript代码。functiongcd(a,b){while(b!=0){temp=a%b;a=b;b=temp;};returna;}console.log((gcd(55,120)))#5比较贬义我国早期也有求最大公约数问题的算法，这就是相减法。中有步骤求最大公约数，使用更多的相位推导技巧：如果可以减半，如果不能减半，则设置母子的个数，以减少与的个数少，多互相减损。关于人数。更相减法来自数的整除性：即如果两个整数a和b可以被c整除，那么a和b的差也可以被C整除。比如求最大公约数98和63的。先看98和63这两个数，因为63不是偶数，所以用大数减去小数得到98-63=35，63-35=2835-28=7，28-7=21，21-7=14，14-7=7。“此时减数和差等于7”，所以98和63的最大公约数是7。再比如求260和104的最大公约数。先看260和104这两个数，都是偶数，所以用2减为130和52，减后130和52也是偶数。继续用2减为65和26，此时65不是偶数，所以大数减去小数65-26=39，39-26=13，26-13=13。此时减数和差值相等，从上面减去两个2，得到的数是13，所以260和104的最大公约数是2×2×13=52。因此，相位归约技术不再是：如果两个整数都是偶数，则使用2归约，直到两个整数不再是偶数，然后执行步骤2。如果两个整数都不是偶数，则转步骤2直接。从较大的数字中减去较小的数字，如果差值恰好等于较小的数字，则停止。否则，对较小的数字和差异重复该过程。第一步减去的2的个数与第二步得到的差值的乘积就是原来两个整数的最大公约数。接下来，我们将编写相位缩减技术的代码。'''@作者：Runsen@微信：RunsenLiu@微信公众号：Python之王@CSDN：https://blog.csdn.net/weixin_44510615@Github：https://github.com/MaoliRUNsen@日期：2020/12/9'''defMaxCommDivisor(m,n):#如果两个整数都是偶数，使用2归约，需要记录归约次数index=1whilem%2==0andn%2==0:m=m/2n=n/2index=index*2#大数减去小数，所以需要判断m和n的大小，保证m最大。ifm
