2 lv N個の最小公倍数

4376 ワード

質問に移動
プログラマは第2段階でN個の最小公倍数問題を解く.
問題を見ても分からないときに見てみましょう.
トラブルシューティングの原理
ユークリッドアーク除去法を用いて最大公約数->最小公約数を求め,最小公約数距離最大公約数->最小公約数を求め,最後に残った最大公約数を求めて問題を解決した.
トラブルシューティング方法
ユークリッドアーク除去法で最大と最小の公倍数を求める式は以下の通りである.
ユークリッドアークほう
最大公約数:
1. 큰 수 % 작은 수
残りが0の場合、小数は最大公約数になります.
2. 작은 수 = 큰 수 % 작은 수, 큰 수 = 작은 수 
上の残りの部分が0でない場合は、2回の演算を実行します.
1つのプロセスで変更された大きな数と小数点をもう一度チェックして、残りの数がゼロであるかどうかを確認します.そうしないと、ステップ2>1を繰り返します.
次に例を示します.
6と8があります.大きいのは8小さいのは6です
8%6 //결과는 2
残りは0ではないので、次の操作を行います.
작은 수 = 8%6 = 2, 큰 수 = 6
残りの値が0であるかどうかを再度比較します.
6%2 //결과는 0
残りは0なので、最大承諾数は2です.
最小公倍数:
1. 큰 수 * 작은 수 / 최대공약수 
最大公約数さえ分かれば、簡単に最小公約数を知ることができる.
次に例を示します.
6と8があります.最大公約数は2
6 * 8 / 2 //결과는 24
最小公倍数は24です.
詳細なトラブルシューティング
上記の内容に基づいて、トラブルシューティングに問題が発生します.この問題は2つの最小公倍数を求めるのではなく、複数の最小公倍数を求める.
上記の情報に基づいて問題を解決するには、アレイ内の2つの要素をグループ化し、演算を実行します.
 for (let i = 0; i < arr.length; i += 2) {
    ... 생략 ...
      }
    }
for文を使用して要素を2つにグループ化します.indexに2を加えたのは,1回の反復でiとi+1を比較したためである.
アレイ内の要素が偶数の場合、問題は大きくありませんが、奇数の場合、最後の要素とundefinedがマージされます.避けるために
 if (i === arr.length - 1) { //i가 마지막 요소일 때, 짝수일경우 이 경우가 발생하지 않는다.
        continue;
      } 
条件を使用すると、最小公倍数を求める演算を行わずに最後の要素をスキップできます.
今から最大公約数を求める公式を作りましょう
最大公約数は、より直感的に見えるように別の関数を設定します.
function 최대(작은값, 큰값) {
  let 작은값보관소;
  while (작은값 != 0) {
    작은값보관소 = 작은값;
    작은값 = 큰값 % 작은값;
    큰값 = 작은값보관소;
  }
  return 큰값;
}
.... 중략 ....
let 최대공약수 = 최대(작은값, 큰값);
小さい値の電子ウェアハウスを選択し、パラメータが渡される小さい値を代入します.
작은값 = 큰값 % 작은값;
このセクションでは、小さな値という変数に残りの変数が含まれているためです.大きな値には、残りの値ではなく、以前の小さな値が含まれている必要があります.そのため、変数として保存します.
次に、最大公約数に基づいて、最小公約数を求めるための大きな値と小さな値をクリアし、最小公約数を加えます.
 let 최소공배수 = (작은값 * 큰값) / 최대공약수;
        arr.splice(i, 2, 최소공배수);
このようにすると、アレイ全体がループされ、大きな値と小さい値を計算して最小公倍数が作成され、アレイのサイズは半分に減少します.
[큰값,작은값,큰값,작은값,큰값,작은값,큰값,작은값] 이었다면
[최소공배수, 최소공배수, 최소공배수, 최소공배수]가 되게됩니다. 
最小公倍数を大きな値、小さな値として繰り返した場合、アレイのサイズは半分に減少し、最終的には1になります.
 while (arr.length !== 1) {
... 최소공배수 반복....
      }
    }
  }
アレイのサイズが1になるまでこの処理を繰り返すと、N個の最小公差数を導出できます.
🧑🏻‍💻 完全なコード
function 최대(작은값, 큰값) {
  let 작은값보관소;
  while (작은값 != 0) {
    작은값보관소 = 작은값;
    작은값 = 큰값 % 작은값;
    큰값 = 작은값보관소;
  }
  return 큰값;
}

function solution(arr) {
  while (arr.length !== 1) {
    for (let i = 0; i < arr.length; i += 2) {
      if (i === arr.length - 1) {
        continue;
      } else {
        let [작은값, 큰값] = [arr[i], arr[i + 1]].sort((a, b) => a - b);
        let 최대공약수 = 최대(작은값, 큰값);
        let 최소공배수 = (작은값 * 큰값) / 최대공약수;
        arr.splice(i, 2, 최소공배수);
      }
    }
  }
  return arr[0];
}
🧑🏻‍💻 問題を解いてから書く
前のステップでは、2つの数の最小公差を求める問題を解決しました.当時ユークリッドアーク除法は知らなかったが失敗し,探索時に見つかった公式はユークリッドアーク除法であった.私はそれをこの問題に適用したのを覚えています.簡単に解決できたようです.コードが長くて、足りない点もたくさんありますが、これからは発展していくので、それはどうですか.
エリートコード分析
次のコードは、プログラマがこの問題の番号を最も多くするコードです.
function nlcm(num) {
 return num.reduce((a,b) => a*b / gcd(a,b))  
}

function gcd(a, b) {
  return a % b ? gcd(b, a%b) : b
}
私の長いコードを6行に圧縮して、世界には多くの達人がいるようです.
さらに発展するために、よく書かれたコードを分析してみましょう.
function gcd(a, b) {
  return a % b ? gcd(b, a%b) : b
}
最大公約数を出すコード
最初のa%bは再帰関数の終了条件と真の一時停止gcd(b,a%b)を実行する.同様に,これもユークリッドアークの方法に基づいて記述されている.
よく観察すると、順序をgcd(b,a%b)に変更し、bを元のa位置に、b位置をa%bの値にする.の双曲線コサインを返します.
a%b->を再配置し、残りの置換を繰り返すと、a%bはいつ0になり、a%bはfalseになり、最大公約数bを返します.
function nlcm(num) {
 return num.reduce((a,b) => a*b / gcd(a,b))  
}
最小公倍数のコードをエクスポートします.
ab/gcd(a,b)では、gcd(a,b)は最大公約数bを返す.
ab/最大公約数.これ自体が最小公倍数であり,reduce関数によって決定される最小公倍数はaであり,配列中の次の順序はbであり,上記の過程を最後まで繰り返す.