题目
存在两个整数a和b,求出它们的最大公约整,比如(15, 18) = 3
暴力枚举法
求两位间最小的那个数min,如果max能整除min,则min是最大公约数;否则,从i = min/2开始遍历(如果除不尽,则向下取整),如果能被a和b两个数都整除,则证明其是最大公约数,如果不能被整除,则i递减重复此操作,直至i为1表示两个数的最大公约数为1
/**
* @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位运算实际上到底做了什么?
发现了吗?
机器码右移1位,对于偶数,就相当于偶数/2的操作;对于奇数,就相当于(奇数/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