SICPで宿題とされていた両替問題の末尾再帰化
今SICPを読んでいるのですが、1.2.2「木の再帰」の章に以下の一文があります。
count-change は、fib の一つ目の実装同様、冗⻑な木の再帰のプロセスを生成 します (292 の計算にはかなりの時間がかかるでしょう)。一方で、答えを計算 するためのよりよいアルゴリズムをどう設計するかというのは自明ではありま せん。この問題は、読者への宿題とします。
これめちゃくちゃ気になってずっと考えていたのですがわからず、調べてみてもメモ化したコードばかりで末尾再帰化したものがありませんでした・・・
そんな諦め掛けていた時以下のコードを見かけました！！
(define (count-change-true-iterative amount)
;; penny is not in the signiture, bacause it equals (- amount
;; (* half-dollar 50)
;; (* quarter 25)
;; (* dime 10)
;; (* nickeli 5))
(define (count-iter sum half-dollar quarter dime nickeli)
(cond ((> (* half-dollar 50) amount)
sum)
((> (+ (* half-dollar 50)
(* quarter 25)) amount)
(count-iter sum(+ half-dollar 1) 0 0 0))
((> (+ (* half-dollar 50)
(* quarter 25)
(* dime 10)) amount)
(count-iter sum half-dollar (+ quarter 1) 0 0))
((> (+ (* half-dollar 50)
(* quarter 25)
(* dime 10)
(* nickeli 5)) amount)
(count-iter sum half-dollar quarter (+ dime 1) 0))
(else (count-iter (+ 1 sum) half-dollar quarter dime (+ nickeli 1)))))
(count-iter 0 0 0 0 0))
(count-change-true-iterative 100)
完璧じゃないですか・・・・！！
50a + 25b + 10c + 5d + e = 100あたりでアプローチを掛けていけばいいとネットでヒントを見つけていたのですが、末尾再帰というワードやSICPの本文中にある木の再帰にとらわれ過ぎて全然思いつかなかったです。
答えをみてみれば簡単なんですよね〜
一見、単にボトムアップで一番価値の低いコインから順に一つづつ場合の数を数えていくだけの地道な方法ですが、SICPのコードと計算時間を比較してみると一目瞭然でした。（100000とかで試してみてください！全然違います！）
いや〜面白い！！
SICP読まれるような方なら説明するまでもないと思いますが、簡単に処理の流れを自分のために書いておきます。
50セント,25セント,10セント,5セント,1セント // コインの価値と種類
<< 1ドル（100セント）を5種類の効果で場合分けする場合 >>
• 前提として1セントは100枚すでに設定されている。そこがスタートになる。
• 1セントは5セントの数で自動的に決まるので考慮に入れない(5セントが19枚の時は自動的に1セントは5枚になる)
• ボトムアップ方式で5からカウントアップしていく
- 1セントのみでまず場合の数をカウントアップ、同時に5セント硬貨の使用枚数を一枚増やす（一通りしかないので1回だけです）
- 5セントと1セントの場合の数を数えあげる（両替に使用する5セント硬貨の使用枚数を増やして、1セント硬貨の使用枚数を減らすイメージ）
- 10セントと5セントと1セントの場合の数を数えあげる(10セント硬貨を1枚増やしたらひたすら5セント硬貨の使用枚数を増やしていき、100を超えたら10セント硬貨を2枚にして5セント硬貨を0からサイドカウントアップ！これを10セント硬貨だけで100を超えるまで繰り返す)
- ....以下同様に続きます