算法的原理：
对于辗转相除法：i和j的最大公约数，也就是i和j都能够除断它。换句话讲，就是i比j的n倍多的那个数k(i = j*n + k，即i % j = k)应该也是最大公约数的倍数。所以就能转换成求k和j的最大公约数。同理，对于更相减损术，同样的道理，i比j大的部分也是最大公约数的倍数。
代码：
1 /** 2 * 求最大公约数算法汇总 3 * 4 */ 5 public class GCD { 6 public static void main(String[] args) { 7 GCD gcd = new GCD(); 8 gcd.gcd1(43, 45); 9 gcd.gcd2(64, 80); 10 gcd.gcd3(45, 81); 11 } 12 13 14 /** 15 * 第三种方法：更相减损术 + 辗转相除法，即 16 * 当a和b均为偶数，gcb(a,b) = 2*gcb(a/2, b/2) = 2*gcb(a>>1, b>>1) 17 * 当a为偶数，b为奇数，gcb(a,b) = gcb(a/2, b) = gcb(a>>1, b) 18 * 当a为奇数，b为偶数，gcb(a,b) = gcb(a, b/2) = gcb(a, b>>1) 19 * 当a和b均为奇数，利用更相减损术运算一次，gcb(a,b) = gcb(b, a-b)， 此时a-b必然是偶数，又可以继续进行移位运算。 20 */ 21 private void gcd3(int i, int j) { 22 System.out.println("The greatest common divisor is:" + doubleGcd(i, j)); 23 } 24 25 private int doubleGcd(int i, int j) { 26 if (i % j == 0) { 27 return j; 28 } 29 30 if ((i&1) == 0 && (j&1) == 0) { 31 // 都是偶数 32 return doubleGcd(i >> 1, j >> 1) << 1; 33 } else if ((i&1) == 0 && (j&1) != 0) { 34 // i为偶数,j为奇数 35 return doubleGcd(i >> 1, j); 36 } else if ((i&1) != 0 && (j&1) == 0) { 37 // i为奇数,j为偶数 38 return doubleGcd(i, j >> 1); 39 } else { 40 // i和j都为奇数 41 return doubleGcd(i, i > j ? i - j : j - i); 42 } 43 } 44 45 46 /** 47 * 第二种方法：九章算术的更相减损术，即如果i>j,那么先用i-j得到其差k.然后将问题转换成求k和m的最大公约数.依此类推,直到差为0. 48 * 这个方法也有一个问题,就是如果i和j想差的比较大,那么这个方法存在较高的时间复杂度. 49 */ 50 private void gcd2(int i, int j) { 51 if (i < j) { 52 gcd2(j, i); 53 return; 54 } 55 56 int k = i - j; 57 if (k == 0) { 58 System.out.println("The greatest common divisor is:" + j); 59 return; 60 } else { 61 if (k >= j) { 62 gcd2(k, j); 63 } else { 64 gcd2(j, k); 65 } 66 } 67 } 68 69 /** 70 * 第一种方法：辗转相除法, 即如果i>j, 那么先用i%j得到余数k.将问题转换成求k和m的最大公约数.依此类推,直到余数为0. 71 * 该方法有一个比较大的问题问题是取模的性能。 72 */ 73 private void gcd1(int i, int j) { 74 // 确保n>m 75 if (i < j) { 76 gcd1(j, i); 77 return; 78 } 79 80 int k = i%j; 81 if (k == 0) { 82 System.out.println("The greatest common divisor is:" + j); 83 return; 84 } else { 85 if (k >= j) { 86 gcd1(k, j); 87 } else { 88 gcd1(j, k); 89 } 90 } 91 } 92 }
黎明前最黑暗，成功前最绝望！
