見出し画像

【アルゴリズム】コインの組み合わせは何通り?javascriptで実装する。


今回はアルゴリズムと言うより、競技プログラミングのお題に近いです。

500 円玉を A 枚、100 円玉を B 枚、50 円玉を C枚持っているとします。これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円となる方法は何通りあるでしょうか?

例えば、100円が何通りあるか調べたいとします。条件は以下です。

 500円 A=2枚  
 100円  B=2枚
 50円 C=2枚
 X=100円
 答え: 2通り

500 円玉を 0 枚、100 円玉を 1 枚、50 円玉を 0 枚選ぶ
500 円玉を 0 枚、100 円玉を 0 枚、50 円玉を 2 枚選ぶ

単純な数で、実際に並べてみるとわかりやすいですね。

実装例

function coins(a, b, c, x) {
 let total = 0;
 let result = 0;

 for (let i = 0; i <= a; i++) {
   for (let j = 0; j <= b; j++) {
     for (let z = 0; z <= c; z++) {
       total = 500 * i + 100 * j + 50 * z;
       if (total === x) result++;
     }
   }
 }
 return result;
}

//console.log(coins(1, 5, 2, 500));


率直にfor文で全探索すれば、解ける問題です。難しい人は、コインの種類を2つに減らしてみましょう。

難しく考えないで、率直さがキーかもしれません。


組み合わせはこの本には登場。全プログラマ必読!


この記事が気に入ったらサポートをしてみませんか?