arrayGcd
求最大公約數(shù)
const arrayGcd = arr =>{
const gcd = (x, y) => !y ? x : gcd(y, x % y);
return arr.reduce((a,b) => gcd(a,b));
}
// arrayGcd([1,2,3,4,5]) -> 1
// arrayGcd([4,8,12]) -> 4
常見(jiàn)面試題 上面用的輾轉(zhuǎn)相除法酪我，即相互取余棕洋，知道最后一方為0椅挣，取另一方遂庄。
麻煩點(diǎn)的寫法
var arrayGcd = function(arr) {
function gcd(x, y) {
return !y ? x : gcd(y, x % y)
}
var result = arr[0];
for(var i = 0, length = arr.length; i < length; i++) {
result = gcd(result, arr[i])
}
return result
}
還有一種方法叫做更相減損法 先兩邊共同把公約數(shù)2除完寥院，然后相減與最小數(shù)比較 知道相等 在算出最先出來(lái)的2余其乘積
var arrayGcd = function(arr) {
function gcd(x, y, z = 0) {
if(!(x % 2 || y % 2)) {
return gcd(x/2, y/2, z+1)
}
return x === y ? x*Math.pow(2, z) : gcd(Math.min(x, y), Math.abs(x - y), z)
}
var result = arr[0];
for(var i = 0, length = arr.length; i < length; i++) {
result = gcd(result, arr[i])
}
return result
}
我們?cè)囍屗?jiǎn)化一點(diǎn)
const arrayGcd = (arr) => {
const gcd = (x, y, z = 1) => x === y ? x * z : x % 2 || y % 2 ? gcd(Math.min(x, y), Math.abs(x - y), z) : gcd(x/2, y/2, z*2)
return arr.reduce((a,b) => gcd(a,b));
}
嗯··· 還是有點(diǎn)長(zhǎng)····
arrayLcm
最小公倍數(shù)
應(yīng)用定理 最大公約數(shù) * 最小公倍數(shù) = 兩數(shù)乘積
所以
const arrayLcm = arr =>{
const gcd = (x, y) => !y ? x : gcd(y, x % y);
const lcm = (x, y) => (x*y)/gcd(x, y);
return arr.reduce((a,b) => lcm(a,b));
}
這個(gè)就簡(jiǎn)單了
