文章参考自书籍：《漫画算法-小灰的算法之旅》-魏梦舒
1.暴力枚举法
最大公约数是我们在小学都学过的，是最基本的数学知识，基本的我们都没有怀疑过它是否有更好的方法去计算。因为笔者当年的老师教我们从最小的数一直往上试，看看能不能同时被这俩整数整除，一直循环下去就能计算出最大公约数了。比如求10和25的最大公约数，大家或许会先试2，发现不是。然后试3，然后4...，一直到5。10/5=2,25/5=5. 2和5已经没有共同可分解的因数了。所以最大公约数是5. 如果用代码来写，可能会稍微有些不同，但是基本思路也是用一个循环去试出来最大的公约数。时间复杂度为O(N). 代码如下：
public static int gcdV1(int a, int b) {
int big = a>b ? a:b;
int small = a<b ? a:b;
if (0==(big%small)) { // 边界条件
return small;
}
for (int i=small/2; i>1; i--) {
if (0==(small%i) && 0==(big%i)) {
return i;
}
}
return 1;
}
2. 辗转相除法
但是如果作为一道面试题，肯定不会这么简单，或许还有更好的方法等着我们去探索。这时候请出我们的欧几里得大神。
欧几里得
他提出了辗转相除法。这个算法是一条定理：两个正整数a和b (a>b), 它们的最大公约数等于a除以b的余数c和b之间的最大公约数。例如25和10,25除以10商2余5，那么25和10的最大公约数等同于10和5的最大公约数。所以在代码中我们可以用这条定理去递归，将比较大的整数运算简化成较小的运算，直到其中较小的数是1(能被较大数整除)为止。代码如下：
public static int gcdV2(int a, int b) {
int big = a>b ? a:b;
int small = a<b ? a:b;
if (0==(big%small)) { // 边界条件
return small;
}
return gcdV2(big%small, small);
}
3. 更相减损术
辗转相除法的思路确实不错，但是其中的a%b取模运算在大整数的情况下性能会比较差劲。这时候还得看我国古代的《九章算术》提出的更相减损术。原理如下：
九章算术
两个正整数a和b (a>b)，它们的最大公约数等于a-b的差值c和较小数b的最大公约数。例如25和10,25减去10的差是15，那么25和10的最大公约数等同于15和10的最大公约数。利用此原理我们可以写出如下代码：
public static int gcdV3(int a, int b) {
if (a == b) { // 边界条件
return a;
}
int big = a>b ? a:b;
int small = a<b ? a:b;
return gcdV3(big-small, small);
}
4. 更相减损与移位相结合
更相减损法确实规避了取模这种性能差的运算，但是递归深度明显增加了。比如计算1000和1的最大公约数会递归999次。要是能结合辗转相除和更相减损的共同优点就好了。所以我们总结出了这样一种gcd算法。规则如下：
-
(1) 当a和b均为偶数时，gcd(a,b) = 2gcd(a/2, b/2)=2gcd(a>>1, b>>1);
-
(2)当a为偶数b为奇数时，gcd(a,b) = gcd(a/2, b)=gcd(a>>1, b);
-
(3)当a为奇数b为偶数时，gcd(a,b) = gcd(a, b/2)=gcd(a, b>>1);
-
(4)当a和b均为奇数时，先利用更相减损术一次 gcd(a,b) = gcd(b, a-b)，此时a-b一定为偶数，然后又可以套用上面的规则继续计算了。
例如我们还是计算25和10的最大公约数，步骤如下。
1.gcd(25,10) = gcd(25, 5)
2.gcd(25,5) = gcd(20,5) // 更相减损术
3.gcd(20,5) = gcd(10,5)
4.gcd(10,5) = gcd(5,5)
5.gcd(5,5)因为两数想等，所以最大公约数是5 // 更相减损术
哦可，talk is cheap, show U the code.
public static int gcdV4(int a, int b) {
if (a == b) { // 边界条件
return a;
}
if (0==(a&1) && 0==(b&1)) {
return gcdV4(a>>1, b>>1)<<1;
} else if (0==(a&1) && 0!=(b&1)) {
return gcdV4(a>>1, b);
} else if (0!=(a&1) && 0==(b&1)) {
return gcdV4(a, b>>1);
} else {
int big = a>b ? a:b;
int small = a<b ? a:b;
return gcdV4(big-small, small);
}
}
注：(a&1)==0说明a是偶数，否则是奇数
- 最小公倍数
最小公倍数等于: (a*b)/gcd(a,b)，这样求解最小公倍数也不在话下了。
作者 @没有故事的老大爷
网友评论