JavaScript求一组数的最小公倍数和最大公约数常用算法详解【面向对象，回归迭代和循环】

下面是JavaScript求一组数的最小公倍数和最大公约数常用算法的详解。

什么是最小公倍数和最大公约数

在数学中，对于给定的两个或多个整数，最小公倍数是可以被其中的每一个整数整除的最小正整数，最大公约数是可以被两个或多个整数整除的最大正整数。最小公倍数和最大公约数常常用于解决各种数学问题，如分数的化简、幂的约分等等。

算法介绍

最大公约数的求解方法

在求两个数的最大公约数时，我们有三种常用的算法：欧几里得算法(辗转相减法和辗转相除法)、更相减损法和移位法。

欧几里得算法

欧几里得算法也称为辗转相减法，通过不断进行两个数的减法来求出它们的最大公约数，直到两个数相等为止。

例如，我们要求出48和60的最大公约数，可以采用如下方法：

1. 用大的数60减去小的数48，得到12
2. 然后用12去重新除以小的数48，得到余数12
3. 再用小的数48除以余数12，得到商4和余数0
4. 因为余数为0，所以48和60的最大公约数是12

其代码实现如下：

function euclidean_algorithm(a, b) {
    while (a !== b) {
        if (a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }
    return a;
}

更相减损法

更相减损法是另一种求最大公约数的方法，它是将两个数较大的减去较小的，然后不断进行减法操作，直到两个数相等为止。

例如，我们要求出48和60的最大公约数，可以采用如下方法：

1. 用大的数60减去小的数48，得到12
2. 再将12和48比较，得到36
3. 然后将36和12比较，得到24
4. 然后将24和12比较，得到12
5. 因为得到的结果是12，所以48和60的最大公约数是12

其代码实现如下：

function subtraction_algorithm(a, b) {
    while (a !== b) {
        if (a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }
    return a;
}

移位法

移位法使用了位运算的技巧，可以更加高效地求解最大公约数。具体做法是：把两个数不断地右移，直到它们相等，然后将它们同时左移相同的位数，最后得到的两个数就是它们的最大公约数。

例如，我们要求出48和60的最大公约数，可以采用如下方法：

1. 把48和60同时右移，得到24和30
2. 再把24和30同时右移，得到12和15
3. 再把12和15同时右移，得到6和7
4. 最后把6和7同时左移2位，得到24
5. 因为得到的结果是24，所以48和60的最大公约数是24

其代码实现如下：

function shift_algorithm(a, b) {
    if (a === 0 || b === 0) {
        return a + b;
    }
    let shift = 0;
    while (((a | b) & 1) === 0) {
        a >>= 1;
        b >>= 1;
        shift++;
    }
    while ((a & 1) === 0) {
        a >>= 1;
    }
    while (b !== 0) {
        while ((b & 1) === 0) {
            b >>= 1;
        }
        if (a > b) {
            let temp = a;
            a = b;
            b = temp;
        }
        b -= a;
    }
    return a << shift;
}

最小公倍数的求解方法

在求多个数的最小公倍数时，我们可以采用如下两种算法：基于最大公约数的求解方法和迭代法。

基于最大公约数的求解方法

最小公倍数与最大公约数是一一对应的，因此可以利用两者的关系来求解最小公倍数。对于两个数a和b，它们的最小公倍数等于a和b的乘积除以它们的最大公约数。

例如，我们要求出12、18和20的最小公倍数，可以采用如下方法：

1. 分别求出12、18和20的最大公约数，分别为6、6和20
2. 由于12、18和20的最大公约数是6，所以它们的最小公倍数是12*18*20/6=720

其代码实现如下：

function lcm_using_gcd(numbers) {
    let lcm = 1;
    for (let i = 0; i < numbers.length; i++) {
        lcm = lcm * numbers[i] / gcd(numbers[i], lcm);
    }
    return lcm;
}

迭代法

迭代法是一种简单的算法，它的基本思想是：计算两个数的最小公倍数，然后再将它与第三个数计算最小公倍数。按这样的方式，不断地进行计算，最后得到所有数的最小公倍数。

例如，我们要求出12、18和20的最小公倍数，可以采用如下方法：

1. 首先计算出12和18的最小公倍数，为36
2. 然后计算36和20的最小公倍数，为180
3. 因为得到的结果是180，所以12、18和20的最小公倍数是180

其代码实现如下：

function lcm_using_iteration(numbers) {
    let lcm = numbers[0];
    for (let i = 1; i < numbers.length; i++) {
        let j = Math.max(lcm, numbers[i]);
        while (j % lcm !== 0 || j % numbers[i] !== 0) {
            j++;
        }
        lcm = j;
    }
    return lcm;
}

示例说明

下面通过两个例子来演示如何使用这些算法来计算最小公倍数和最大公约数。

示例1

假设我们要求出35和42的最大公约数和最小公倍数，可以采用如下方法：

let result1 = euclidean_algorithm(35, 42);
let result2 = subtraction_algorithm(35, 42);
let result3 = shift_algorithm(35, 42);
let result4 = lcm_using_gcd([35, 42]);
let result5 = lcm_using_iteration([35, 42]);
console.log('35和42的最大公约数是：', result1, result2, result3);
console.log('35和42的最小公倍数是：', result4, result5);

输出结果：

35和42的最大公约数是： 7 7 7
35和42的最小公倍数是： 210 210

示例2

假设我们要求出12、18和20的最大公约数和最小公倍数，可以采用如下方法：

let result1 = euclidean_algorithm(euclidean_algorithm(12, 18), 20);
let result2 = subtraction_algorithm(subtraction_algorithm(12, 18), 20);
let result3 = shift_algorithm(shift_algorithm(12, 18), 20);
let result4 = lcm_using_gcd([12, 18, 20]);
let result5 = lcm_using_iteration([12, 18, 20]);
console.log('12、18和20的最大公约数是：', result1, result2, result3);
console.log('12、18和20的最小公倍数是：', result4, result5);

输出结果：

12、18和20的最大公约数是： 2 2 2
12、18和20的最小公倍数是： 180 180

以上是JavaScript求一组数的最小公倍数和最大公约数常用算法的完整攻略，其中包含了算法的介绍及具体的示例说明。