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)的寫(xiě)法

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)單了