両替の計算
昔、この話を説明してもらった時に、いまいち両替のアルゴリズムがよくわからなかった。
それで、今日電車の中で読んでも、やっぱりもやもやしてしまったので、一度、整理してみよっと。
http://kreisel.fam.cx/webmaster/clog/2008-06-09-1.html
を参考にさしてもらったのだが、要は組み合わせの計算をしているわけだ。両替となると面倒なので、組み合わせの計算と考えると、『5種類の硬貨を使って、1ドルを作り上げる組み合わせは、全部で何通りですか？』となる。
とすると、Combinationを使えば、理解しやすく、nCmを計算するだけで良い(nが硬貨の種類。mが目標の金額を達成するための数)。
ここで、またわかりにくいのが、Combinationをそのまま解けばいいじゃん、と言うのではなく、再帰的なやり方をしていること。
アルゴリズムの英文をそのまま書くと、
- the number of ways to change amount a using all but the first kind coin, plus
- the number of ways to change amount a - d using all n kinds of coins, where d is the denomination of the first kind of coin.
うぅ〜、何のことかわからん。
とりあえず、噛み砕いて組み合わせの問題にすると、5種類のカードから3種類のカードを選択する場合
- 最初に選択したカード以外の4種類のカードたちから3種類を選択する
- 最初に選択したカードを必ず含めて、残りの4種類のカードから2種類を選択する
- 組み合わせの数は、1と2の和になります。
と言うことでおk?
遠い昔に習ったような気がするのだが、n種類の中からm個を選択する組み合わせは、上記のやり方で
