求解最大公约数
一 写在开头
1.1 本节内容
本节主要内容为几种常见的两个数的最大公约数（Greatest Common Divisor）的求法。
二 辗转相除法
2.1 辗转相除法原理
辗转相除法也叫欧几里得算法，是一种非常古老的求解两个数的最大公约数的算法。其基于的原理：两个正整数a和b（a > b），它们的最大公约数gcd等于a除以b的余数r和b之间的最大公约数。比如，10和25的最大公约数5等于25除以10的余数5和10的最大公约数；再比如51和21的最大公约数3等于51除以21的余数9和21的最大公约数，而9和21的最大公约数为3。根据上面的原理，辗转相除法的算法流程可以如下：
步骤1：计算a与b的余数r。
步骤2：如果r为0，则返回gcd = b。否则，转到步骤3。
步骤3：使用b的值更新a的值，使用余数r更新b的值，转到步骤1。
2.2 辗转相除法的C语言实现
1 long GetGCD(long a, long b)2 {3 return (a % b == 0) ? b : GetGCD(b, a%b);4 }等等，为什么不对a和b的大小进行判断呢？上面的算法原理中不是要求a大于b吗？如果调用时a值大于b值，比如a为51，b为21，那么情况跟上述算法原理是相符的。如果调用时a值小于b值，比如a为21，b为51，那么，21除以51的余数r为21，不为0，于是接着调用GetGCD(51, 21)，看到了没？这就和a > b的情况是一样的了。也就是说我们根本无需判断a和b的大小，当a值小于b值时，算法的下一次递归调用就能够将a和b的值交换过来。
2.3 辗转相除法的缺点
辗转相除法实现时因为使用了求余运算的缘故导致其在面对大整数的时候性能不够理想。我们应尽量避免使用求余运算。接下来介绍另一种最大公约数求解法。
三 更相减损术
3.1 更相减损术原理
更相减损术出自《九章算术》，其原理很简单：两个正整数a和b（a > b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。依次递归下去，直到两个数相等。这相等两个数的值就是所求最大公约数。
3.2 更相减损术的C语言实现
1 long GetGCD(long a, long b)2 {3 if (a == b)4 return a;5 else if (a > b)6 return GetGCD(a-b, b);7 else8 return GetGCD(b-a, a);9 }
3.3 更相减损术的缺点
更相减损术虽然避免了求余运算，但当两个数a和b相差太过悬殊时，递归的次数会非常多，严重影响算法性能。比如当a为100000，b为1时，算法要递归99999次。
四 终极版本
一般情况下，以上两个版本完全够用。如果追求最佳算法性能的终极版本，那就去看《编程之美》第2.7节吧。
五 参考资料
1. 《编程之美》
原文https://www.cnblogs.com/laizhenghong2012/p/8457784.html
微信扫一扫，打赏阿沐吧～
评论