複数数の最大公約数、最小公倍数アルゴリズム

まず,著者らは,相除去法と更相減損術を転々とすると仮定した.
2つの数の最大公約数(GCD)、最小公倍数(LCM)は上記の2つのアルゴリズムで実現するのは非常に簡単である.では、同時に複数の数を求めるとしたら?
まず2つの数の最大公約数を約定する関数はgcdであり、最小公倍数の関数はlcmである.
複数数の最大公約数アルゴリズム

は、すべての数が計算されるまで、前のステップの最大公約数と次の数を2つの数で計算し続けることを自然に考えます.

function multi_gcd_step() {
   //     ，      
   let arr = Array.from(arguments).map(a => a > 0 ? a : -a);
   //       
   if (arr.length < 2) {
       throw new Error('        2');
   }
   if (arr.some(a => !a)) {
       throw new Error('      0');
   }
   for (let i = 0; i < arr.length - 1; i++) {
       let c = gcd(arr[i], arr[i + 1]);		// gcd            
       if (c === 1) {
           //         1，     
           return 1;
       }
       arr[i + 1] = c;
   }
   return arr[arr.length - 1];	//       
}

上のアルゴリズムは、内部に複数回循環するgcdアルゴリズムを絶えず呼び出すため、面倒である.実は、転がり相殺法によって、私たちはこのようにすることができます.

このセットの数をソート(大きいから小さい)

は、2つの隣接する2つの数ごとに、隣接する2つの数をAとBとする(Aは前であり、既に並べ替えられているのでA>B)、A=n*B(nは整数)、すなわちAがBで割り切れる場合、A=Bとする.AがBによって除去されない場合、A=A%Bとする.

は、配列内の各数が等しくなるまで、上記の2つのステップを繰り返します.最大公約数はこの数です.

function multi_gcd_zzxcf() {
    //     
    let arr = Array.from(arguments).map(a => a > 0 ? a : -a);
    // TODO:       
    while (!arr.every(a => a === arr[0])) {
        //       
        arr.sort((a, b) => b - a);
        //        A，    B
        //   A   B  ，    A = B；  A   B    A = A % B
        for (let i = 0; i < arr.length - 1; i++) {
            let c = arr[i] % arr[i + 1];
            arr[i] = c || arr[i + 1];
        }
    }
    return arr[0];
}

複数数の最小公倍数アルゴリズム
2つの数a,bの最小公倍数アルゴリズムはab/gcd(a,b)であり,すなわち両者の積をそれらの最大公約数で除算することを知った.そんなにたくさんの数のものもこのように計算できますか?答えは否定的で、例えば(9,10,5)、最大公約数は1で、最小公倍数は90≠9です.× 10 × 5 ÷ 1.従って、上記の複数の数の最大公約数アルゴリズムに基づいてはならない.

は2つの数の最小公倍数を絶えず計算し、前のステップの最小公倍数と次の計算を遍歴するまで、最終的な結果はすべての数の最小公倍数

である.

function multi_lcm_step() {
	let arr = Array.from(arguments).map(a => a > 0 ? a : -a);
	// TODO:       
    for (let i = 0; i < arr.length - 1; i++) {
        arr[i + 1] = lcm(arr[i], arr[i + 1]);	// lcm             
    }
    return arr[arr.length - 1];
}

計算m=a1*a2*..*an

a 1,a 2,...,anのすべてのaiをm/aiで

に置き換える

はa 1,a 2,...,anの中の最小非ゼロ項ajを見つけ,複数の最小非ゼロ項があれば1つの

を任取する.

aj以外のすべての非0項akはak%ajで置き換えられる.aj以外が0になると(6)

に移る.

から(3)

へ

の最小公倍数はm/aj

である.

function multi_lcm_zzxcf() {
    let arr = Array.from(arguments).map(a => a > 0 ? a : -a);
    // TODO:       
    let m = arr.reduce((a, b) => a * b, 1);
    arr = arr.map(a => m / a);
    let aj = m;
    do {
        //   0   
        let ajIndex = -1;
        for (let i = 0; i < arr.length; i++) {
            if (arr[i] < aj) {
                aj = arr[i];
                ajIndex = i;
            }
        }
        //        ，     
        for (let i = 0; i < arr.length; i++) {
            if (i !== ajIndex) {
                arr[i] = arr[i] % aj;
            }
        }
        //    0，       
        arr = arr.filter(a => !!a);
    } while (arr.length);
    return m / aj;
}

リファレンス接続:https://www.cnblogs.com/leiyuxiang/articles/3494977.html