javascript アルゴリズム

はじめに

shiftBの課題に関係ない内容だと思います笑
今回は、最近発売されJavaScriptによるアルゴリズム入門の本についてです！
読んでいて気づきまたはヒントになるのではないか！と思い書いてみました！😳
まだ、全然読み進められてない(難しすぎて笑)😂

漸化式

漸化式は、数学的・計算的な問題を解くのに使われる手法です！
色々な用途で使用されますが、今回は組み合わせの数についての内容です!

組み合わせの数の基本的な考え方

組み合わせとは？
あるグループから特定の数の選ぶ方法の数を計算するというものです。
これを「組み合わせの数」と言い、数学的には「nCr」と表記されます。
もう何言ってるか分からいですよね笑😂

例

例えば、あなたが10個のフルーツを持っているとします。
その中から3個を選ぶ方法を考えるとする。
ここで重要なのが、どのフルーツを選ぶかだけで、選ぶ順番は関係ないです。
以下のコードは、10個のフルーツの中から3個を選ぶ組み合わせの数はどれぐらいなのか？とういものです。

function combi(n, r) { 
let p = 1;  
for(let i = 1; i <= r; i++) {　
p = p * (n - i + 1) / i;  
}  
return p;
}

let n = 10;
let r = 3;
let result = combi(n, r);
console.log(`10個のフルーツから3個を選ぶ組み合わせの数は: ${result}`);

コンソール結果

10個のアイテムから3個を選ぶ組み合わせの数は: 120

120！！
そんなにあるのか！！笑笑

組み合わせの使った、コードの特徴

1. 関数定義と初期化
   特徴: 初期化
   この初期化は、組み合わせの計算を始める準備。
   pは計算結果を保持する変数で、1で初期化している。
   
   nは、選ぶ対象フルーツの総数。10
   rは、選びたいフルーツの数を表す。3

function combi(n, r) {
 let p = 1;

2. ループ設定
   特徴: 反復処理
   このループは、1からrまでの整数に対して繰り返し処理を行う。
   iは「今何回目の計算をしているか」を示しています。

for(let i = 1; i <= r; i++) {

3. 漸化式の計算

   特徴: 漸化式の適用

   今回、ここが漸化式の核心部分です。
   (n - i + 1)は、選択可能なフルーツの数を減らしながら掛け算を行っています。
   nからiを引いて1を足すことで、選べるアイテムの数を調整しています。

   つまり、この部分は選べるフルーツの数を段階的に減らしながら掛け算を行っているっということです！
   

   p = p * (n - i + 1) / i;

   
   
   
   具体例

   (n - i + 1)

   
   初めて選ぶ時、i = 1

   最初に選べるフルーツは10個。
   

   2回目選ぶ時は、i = 2

   n = 10なので、`10 - 2 + 1 = 9`。

   2回目に選ぶフルーツは9個に減る。
   
   3回目に選ぶときは、i = 3

   n = 10なので、`10 - 3 + 1 = 8`。

   3回目に選ぶフルーツは8個に減る。

   このように、選ぶたびに選択肢が一つずつ減っていく仕組みです。

/i

/iは、なにをしているのか。
初めて選ぶ時、i = 1
割る数は1。計算に影響ないです。

2回目選ぶ時、i = 2
割る数は2。２つの選びた方の順番が異なっても同じ組み合わせとして数えるため。

3回目選ぶ時、i = 3
割る数は3。同様に選びたかの順番を調整する。

これらの計算方法でできることは、10個のフルーツを3個選ぶ組み合わせの数を効率的にもとめることができる。
選べるフルーツを減らしながら掛け算し、選ぶ順番の重複を避けるために割り算を行います。これによって、最終的に正しい組み合わせの数を得られるというわけです。

おわり

今回、漸化式の組み合わせの数を知って気づいたのですが、
今回の実装方法で他に活用できることは、
メニューから料理を選ぶ時や大きな数字を扱うときに簡単に計算できたり。
コンピューターの処理を早くできるメリットがあります。

アルゴリズムを学ぶことで、実装の選択肢を増やせるってことに気づけました。
全然できていないけど、コツコツやる価値があると個人的に思っています。