SICP 両替の計算
次の問題を考えてみてください。 1 ドルを両替する やり方はいくつあるでしょうか。 使うのは、50 セント、25 セント、10 セント、 5 セント、1 セントのコインです。 より一般的には、任意の金額に対して両替 のパターン数を計算する手続きを書くことはできるでしょうか。
n種類の硬貨を使う, 金額aの両替の場合の数は: • (A)最初の種類の硬貨以外を使う, 金額aの両替の場合の数, 足す • (B)dを最初の硬貨の額面金額[denomination]として, n種類の硬貨を使う, 金額a - dの両替の場合の数
上記から下記が導かれるらしい。
• aがちょうど0なら, 両替の場合の数は1 • aが0より少なければ, 両替の場合の数は0 • nが0なら, 両替の場合の数は0
再帰的に書くと下記になるらしい。
(define (count-change amount) (cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount (- kinds-of-coins 1))
(cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
よくわからん。ちょっと落ち着いて冷静に考えてみる。
まず、金額aをn種類の硬貨で両替するには、最初の硬貨を使う場合の数と使わない場合の数の合計になる。 例えば、a=15セント、n=[10セント、5セント, 1セント]とすると、10セントを使って両替した場合の数と10セントを使わなかった場合の数の合計が答えになる。ここまでわかる。
じゃあ10セントを使って両替する場合を数えてみる。(A)
10セントを使うということは必ず10セントを使う必要があるので、まずは10セントを引いちゃう。
そうすると残り5セントを両替する場合の数を数えれば良いので、a=5として、上記と同じフローを踏む。
5セントを10セントを使って両替した場合の数と10セントを使わなかった場合の数の合計を求める。
5セントを10セントを使って両替しようとすると0以下になるので、この分岐は終了となり、次は5セントを10セントを使わない分岐の計算に入る。
10セントを使わない分岐というのは、5セントを5セントと1セントを使って計算するということので、上記と同じように5セントを使う場合と使わない場合を足せば良い。
というふうにどんどん続けて行けばAの答えが求められるはず、ということ。
次に10セントを5セントを使わないで両替する場合を数えてみる。(B)
5セントを使わないということは、使う硬貨の種類から1引いたもので、上記と同じことをやる。
なので、10セントを5セントと1セントで両替するということ。
これは同じように5セントを使った場合の数と使わなかった場合の数を足せば求められる。
なので上記と同様の計算をどんどん続ければBの答え場求められるはず。
書いててなんのこっちゃという感じだけど、なんとなくわかった気がする。
ただこれを自ら思いつくのは今の自分にとってはなかなか発想の転換が必要だなぁ。