第1章(3)
問題1.14
まずcount-changeが何をしているのか把握する。正直説明の日本語が分かりにくいためか、すぐには理解できなかった。
amountセントを、kinds-of-coins種類のコインで両替する場合の数を求める関数がcc関数。なお、コインの種類が1種類のときは1セントコインのみ、2種類のときは1セントと5セント、というように、first-denomination関数のcond式の上から順に使用する。
例えば1セントを5種類のコインで両替する場合は1セント1個にするしかないので1。5セントのときは1セントx5と5セントx1があるので2。こんな感じで実際に試してみると以下のようになる。
(cc 1 5) ; → 1 (cc 5 5) ; → 2 (cc 10 5); → 4
cc関数のアルゴリズムは、両替の場合の数を2種類に分けて計算する。仮に15セントを、1,5,10セントコインの3種類を使って両替すると場合（つまり(cc 15 3)）、は以下のように分ける。
- 10セントをコインを使わない場合、つまり(cc 15 2)。
- 10セントコインを少なくとも一つ使う場合。このときの場合の数は残り5セントを両替する場合、つまり(cc 5 2)となる。
この2つを足してやれば再帰的に計算できる。上の式はkinds-of-coinsが減り、下の式はamountが減り、最終的にはどちらも0以下になる。再帰の終了条件は本に描いてあるとおり。
では問題のケース(count-change 11 5)の手続きの木構造を作ってみる。上から下に広がる木は書きにくいので右下に広がるように書いてみる。なお、右のコメントはその関数が返す値。
(cc 11 5) ; 4 +-> (cc 11 4) ; 4 | +-> (cc 11 3) ; 4 | | +-> (cc 11 2) ; 3 | | | +-> (cc 11 1) ; 1 | | | | +-> (cc 11 0) ; 0 | | | | +-> (cc 10 1) ; 1 | | | | +-> (cc 10 0) ; 0 | | | | +-> (cc 9 1) ; 1 | | | | +-> (cc 9 0) ; 0 | | | | +-> (cc 8 1) ; 1 | | | | +-> (cc 8 0) ; 0 | | | | +-> (cc 7 1) ; 1 | | | | +-> (cc 7 0) ; 0 | | | | +-> (cc 6 1) ; 1 | | | | +-> (cc 6 0) ; 0 | | | | +-> (cc 5 1) ; 1 | | | | +-> (cc 5 0) ; 0 | | | | +-> (cc 4 1) ; 1 | | | | +-> (cc 4 0) ; 0 | | | | +-> (cc 3 1) ; 1 | | | | +-> (cc 3 0) ; 0 | | | | +-> (cc 2 1) ; 1 | | | | +-> (cc 2 0) ; 0 | | | | +-> (cc 1 1) ; 1 | | | | +-> (cc 1 0) ; 0 | | | | +-> (cc 0 1) ; 1 | | | +-> (cc 6 2) ; 2 | | | +-> (cc 6 1) ; 1 | | | | +-> (cc 6 0) ; 0 | | | | +-> (cc 5 1) ; 1 | | | | +-> (cc 5 0) ; 0 | | | | +-> (cc 4 1) ; 1 | | | | +-> (cc 4 0) ; 0 | | | | +-> (cc 3 1) ; 1 | | | | +-> (cc 3 0) ; 0 | | | | +-> (cc 2 1) ; 1 | | | | +-> (cc 2 0) ; 0 | | | | +-> (cc 1 1) ; 1 | | | | +-> (cc 1 0) ; 0 | | | | +-> (cc 0 1) ; 1 | | | +-> (cc 1 2) ; 1 | | | +-> (cc 1 1) ; 1 | | | | +-> (cc 1 0) ; 0 | | | | +-> (cc 0 1) ; 1 | | | +-> (cc -4 2) ; 0 | | +-> (cc 1 3) ; 1 | | +-> (cc 1 2) ; 1 | | | +-> (cc 1 1) ; 1 | | | | +-> (cc 1 0) ; 1 | | | | +-> (cc 0 1) ; 0 | | | +-> (cc -4 2) | | +-> (cc -9 3) ; 0 | +-> (cc -14 4) ; 0 +-> (cc -39 5) ; 0
実際の実行もこの図の上から順に行われる。試しに以下のように引数を表示する機能をcc関数に追加してみる。
(define (cc amount kinds-of-coins) (display (format "amout: ~a, kinds-of-coins: ~a\n" 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)))))
実行結果はこんな感じ。
amout: 11, kinds-of-coins: 5 amout: 11, kinds-of-coins: 4 amout: 11, kinds-of-coins: 3 amout: 11, kinds-of-coins: 2 amout: 11, kinds-of-coins: 1 amout: 11, kinds-of-coins: 0 amout: 10, kinds-of-coins: 1 amout: 10, kinds-of-coins: 0 amout: 9, kinds-of-coins: 1 amout: 9, kinds-of-coins: 0 amout: 8, kinds-of-coins: 1 amout: 8, kinds-of-coins: 0 amout: 7, kinds-of-coins: 1 amout: 7, kinds-of-coins: 0 amout: 6, kinds-of-coins: 1 amout: 6, kinds-of-coins: 0 amout: 5, kinds-of-coins: 1 amout: 5, kinds-of-coins: 0 amout: 4, kinds-of-coins: 1 amout: 4, kinds-of-coins: 0 amout: 3, kinds-of-coins: 1 amout: 3, kinds-of-coins: 0 amout: 2, kinds-of-coins: 1 amout: 2, kinds-of-coins: 0 amout: 1, kinds-of-coins: 1 amout: 1, kinds-of-coins: 0 amout: 0, kinds-of-coins: 1 amout: 6, kinds-of-coins: 2 amout: 6, kinds-of-coins: 1 amout: 6, kinds-of-coins: 0 amout: 5, kinds-of-coins: 1 amout: 5, kinds-of-coins: 0 amout: 4, kinds-of-coins: 1 amout: 4, kinds-of-coins: 0 amout: 3, kinds-of-coins: 1 amout: 3, kinds-of-coins: 0 amout: 2, kinds-of-coins: 1 amout: 2, kinds-of-coins: 0 amout: 1, kinds-of-coins: 1 amout: 1, kinds-of-coins: 0 amout: 0, kinds-of-coins: 1 amout: 1, kinds-of-coins: 2 amout: 1, kinds-of-coins: 1 amout: 1, kinds-of-coins: 0 amout: 0, kinds-of-coins: 1 amout: -4, kinds-of-coins: 2 amout: 1, kinds-of-coins: 3 amout: 1, kinds-of-coins: 2 amout: 1, kinds-of-coins: 1 amout: 1, kinds-of-coins: 0 amout: 0, kinds-of-coins: 1 amout: -4, kinds-of-coins: 2 amout: -9, kinds-of-coins: 3 amout: -14, kinds-of-coins: 4 amout: -39, kinds-of-coins: 5
木構造と同じ順になっていることが分かる。
何か一問あたりにかかる時間が長くなってる。最後まで持つんだろうか...。
