【アルゴリズム】コインの組み合わせは何通り?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つに減らしてみましょう。
難しく考えないで、率直さがキーかもしれません。
組み合わせはこの本には登場。全プログラマ必読!
この記事が気に入ったらサポートをしてみませんか?