[算法]数学

练习题

:::warning

• 实现加减乘除
• 实现大数运算
• 1447. 最简分数 :::

pow(x, n)

50. Pow(x, n) (剑指 Offer 16. 数值的整数次方)

var myPow = function(x, n) {
    res = 1;
    if (n < 0) {
        x = 1 / x;
        n *= -1;
    }
    // 考虑到i是小数，故0为分界点
    for (let i=n; i!=0; i=Math.floor(i/2)) {
        if (i % 2 != 0) {
            res *= x;
        }
        x *= x;
    }
    return res;
};

最大公约数 gcd

:::success // a < b
function gcd(a: number, b: number): number {
if (a > b) [a, b] = [b, a];
while (a) {
[a, b] = [b % a, a];
}
return b;
}

// a < b
function gcd(a, b) {
return a == 0 ? b : gcd(b % a, a);
} :::

// a < b
function gcd(a, b) {
    if (a == 0) return b;
    return gcd(b % a, a);
}

gcd(2, 6) // 2
gcd(4, 6) // 2
gcd(6, 9) // 3

最小公倍数 lcm

加穷举

将大数依次加1，对得到的数判断其是否可整除两数。

function LCM(n1, n2) {
    let res = n1 < n2 ? n2 : n1;
    while (res % n1 != 0 || res % n2 != 0) {
        res++;
    }
    return res;
}

乘穷举

将大数依次乘N（N为从1开始的自然数），对得到的数判断其是否整除小数。

function LCM(n1, n2) {
    let max = n1 < n2 ? n2 : n1;
    let res = max;
    let min = 1;
    while (res % n1 != 0 || res % n2 != 0) {
        min++;
        res = max * min;
    }
    return res;
}

借助：最大公约数

最小公倍数=两整数的乘积÷最大公约数

function LCM(n1, n2) {
    let res = n1 * n2 / GCD(n1, n2)
    return res;
}

function GCD(n1, n2) {
    if (n1 > n2) {
        [n1, n2] = [n2, n1]
    }
    while (n2 != 0) {
        [n1, n2] = [n2, n1 % n2]
    }
    return n1;
}