算法练习2：求最大公约数（辗转相除法、更相减损法）
题目
存在两个整数a和b，求出它们的最大公约整，比如(15, 18) = 3
暴力枚举法
求两位间最小的那个数min，如果max能整除min，则min是最大公约数；否则，从i = min/2开始遍历(如果除不尽，则向下取整)，如果能被a和b两个数都整除，则证明其是最大公约数，如果不能被整除，则i递减重复此操作，直至i为1表示两个数的最大公约数为1
- 时间复杂度：O(min(a, b))
/**
* @description 求两个整数最大公约数
* @param a:整数
* @param b:整数
* @return greatestDivisor: 最大公约数
*/
// 暴力枚举法
function getCommonDivisor(a, b) {
let min = a > b ? b : a;
let max = a > b ? a : b;
if(max%min === 0) {
return min;
}
for(let i = Math.floor(min/2); i > 1; i--) {
if(min%i===0 && max%i===0) {
return i;
}
}
return 1;
}
console.log(getCommonDivisor(15,18)); // 3
辗转相除法
辗转相除法，也叫欧几里得算法，它基于一个定理：两个整数a和b(a>b),它们的最大公约数等于a除以b的余数和b之间的最大公约数
也就是(a, b) = (a%b, b)
- 时间复杂度：不好计算，因为每次除数是不确定的，只能近似为：O(log(max(a, b)))
// 辗转相除法
function getCommonDivisor2(a, b) {
let min = a > b ? b : a;
let max = a > b ? a : b;
if(max%min === 0) {
return min;
}
return getCommonDivisor2(max%min, min);
}
console.log(getCommonDivisor2(8,9));
更相减损法
更相减损法，也叫更相减损术，是出自《九章算术》的一种求最大公约数的算法，它的原理是：两个正整数a和b(a>b),它们的最大公约数等于a-b的差值和b之间的最大公约数，它可以弥补当a和b整数都过大时，取模运算符性能较差的问题。
但同时，它也有自己的问题，当a和b之间的差距过大，使用更相减损法运算次数要比辗转相除法要多得多，比如10000和1，做减法的话，递归次数为9999次；而使用辗转相除法只用1次就可以了。
即 (a, b) = (a-b, b)
- 时间复杂度：避免了取模运算，O(max(a, b))
// 更相减损法
function getCommonDivisor3(a, b) {
// 当a等于b时，就是这两个数的最大公约数
if(a === b) {
return a;
}
let min = a > b ? b : a;
let max = a > b ? a : b;
return getCommonDivisor3(max-min, min);
}
console.log(getCommonDivisor3(10,25)); // 5
辗转相除法和更相减损法相结合+移位运算
因为移位运算符的性能要比取模和乘除的性能高，所以我们往往可以使用位运算来替代这些操作。
-
右移位运算 >>
观察一下，右移1位运算实际上到底做了什么？-
偶数：
1000(8) 右移一位=> 0100(4)
0100(4) 右移一位=> 0010(2)
0010(2) 右移一位=> 0001(1) -
奇数右移一位的二进制：
0111(7) 右移一位=> 0011(3)
0101(5) 右移一位=> 0010(2)
0011(3) 右移一位=> 0001(1)
发现了吗？机器码右移1位，对于偶数，就相当于偶数/2的操作；对于奇数，就相当于(奇数/2)向下取整操作
利用这个特性，可以使用移位运算符替代辗转相除法中的除法操作
-
-
左移位运算
-
偶数：
0010(2) 左移一位 0100(4)
0100(4) 左移一位 1000(8) -
奇数左移：
0001(1) 左移一位=> 0010(2)
0011(3) 左移一位=> 0110(6)
0101(5) 左移一位=> 1010(10)
左移位运算1无论对于奇偶数，都是乘2的操作
-
-
与运算 &
只要是偶数，与1的机器码相与，就会返回为0，利用这个特性，我们可以使用&来替代取模运算
2：0010
1：0001
&：0000
在了解位运算后，我们来看下怎么结合辗转相除法和更相减损法来得到最优解：
- 当a和b都为偶数时，(a, b) = 2* (a/2, b/2) = (a>>1, b>>1) <<1
- 当a为偶数，b为奇数时，(a, b) = (a/2, b) = (a>>1, b)
- 当b为偶数，a为奇数时，(a, b) = (a, b/2) = (a, b>>1)
- 当a和b都为奇数时，先利用更相减损法运算一次, (a, b) = (a-b, b)，之后，a-b结果为偶数，又可以继续进行位运算了
// 使用位运算，结合辗转相除和更相减损法
function getCommonDivisor4(a, b) {
if(a === b) {
return a;
}
// a,b都为偶数，(a, b) = (a/2, b/2)
if((a & 1 === 0) && (b & 1 === 0)) {
return getCommonDivisor4(a>>1, b>>1) <<1
// a为偶数，b为奇数，(a, b) = (a/2, b)
}else if((a & 1 === 0) && (b & 1 !== 0)) {
return getCommonDivisor4(a>>1, b)
// a为奇数，b为偶数，(a, b) = (a, b/2)
}else if((a & 1 !== 0) && (b & 1 === 0)) {
return getCommonDivisor4(a, b>>1)
// a,b都为奇数
}else {
let big = a > b ? a : b
let small = a < b ? a : b
return getCommonDivisor4(big-small, small)
}
}
console.log(getCommonDivisor4(10,25)); // 5
