SICP 問題1.14
1.2.3 増加の程度 - 計算機プログラムの構造と解釈 第二版
1.2.2節のcount-change手続きが11セントの両替の場合に生成するプロセスを示す木構造を描け.
両替の金額の増加につれ, このプロセスが使うスペースとステップ数の増加の程度は何か.
とりあえず1.2.2のcount-changeの実装を持ってくる。
(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))
Q. 生成するプロセスを示す木構造を描け
木構造を書くのはここだとめんどくさいので、どのように展開されるのかを書く。
11セントの両替の場合は下記のように展開される。
(count-change 11)
(cc 11 5)
(+ (cc 11 4) (cc (- 11 50) 5))
(+ (cc 11 4) 0)
(cc 11 4)
(+ (cc 11 3) (cc (- 11 25) 4))
(+ (cc 11 3) 0)
(cc 11 3)
(+ (cc 11 2) (cc (- 11 10) 3))
(+ (cc 11 2) (cc 1 3))
(+ (cc 11 2) (+ (cc 1 2) (cc (- 1 10) 3)))
(+ (cc 11 2) (+ (cc 1 2) 0))
(+ (cc 11 2) (cc 1 2))
(+ (cc 11 2) (+ (cc 1 1) (cc (- 1 5) 2)))
(+ (cc 11 2) (+ (cc 1 1) 0))
(+ (cc 11 2) (cc 1 1))
(+ (cc 11 2) (+ (cc 1 0) (cc (- 1 1) 1)))
(+ (cc 11 2) (+ (cc 1 0) (cc 0 1)))
(+ (cc 11 2) (+ (cc 1 0) 1))
(+ (cc 11 2) (+ 0 1))
(+ (cc 11 2) 1)
(+ (+ (cc 11 1) (cc (- 11 5) 2)) 1)
(+ (+ (cc 11 1) (cc 6 2)) 1)
(+ (+ (cc 11 1) (+ (cc 6 1) (cc (- 6 5) 2))) 1)
(+ (+ (cc 11 1) (+ (cc 6 1) (cc 1 2))) 1)
(+ (+ (cc 11 1) (+ (cc 6 1) (+ (cc 1 1) (cc (- 1 5) 2)))) 1)
(+ (+ (cc 11 1) (+ (cc 6 1) (+ (cc 1 1) 0))) 1)
(+ (+ (cc 11 1) (+ (cc 6 1) (cc 1 1))) 1)
(+ (+ (cc 11 1) (+ (cc 6 1) (+ (cc 1 0) (cc (- 1 1) 1)))) 1)
(+ (+ (cc 11 1) (+ (cc 6 1) (+ (cc 1 0) (cc 0 1)))) 1)
(+ (+ (cc 11 1) (+ (cc 6 1) (+ (cc 1 0) 1))) 1)
(+ (+ (cc 11 1) (+ (cc 6 1) (+ 0 1))) 1)
(+ (+ (cc 11 1) (+ (cc 6 1) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (cc (- 6 1) 1)) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (cc 5 1)) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (cc (- 5 1) 1))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (cc 4 1))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) (cc (- 4 1) 1)))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) (cc 3 1)))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) (+ (cc 3 0) (cc (- 3 1) 1))))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) (+ (cc 3 0) (cc 2 1))))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) (+ (cc 3 0) (+ (cc 2 0) (cc (- 2 1) 1)))))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) (+ (cc 3 0) (+ (cc 2 0) (cc 1 1)))))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) (+ (cc 3 0) (+ (cc 2 0) (+ (cc 1 0) (cc (- 1 1) 1))))))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) (+ (cc 3 0) (+ (cc 2 0) (+ (cc 1 0) (cc 0 1))))))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) (+ (cc 3 0) (+ (cc 2 0) (+ (cc 1 0) 1)))))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) (+ (cc 3 0) (+ (cc 2 0) (+ 0 1)))))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) (+ (cc 3 0) (+ (cc 2 0) 1))))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) (+ (cc 3 0) (+ 0 1))))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) (+ (cc 3 0) 1)))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) (+ 0 1)))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ (cc 4 0) 1))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) (+ 0 1))) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ (cc 5 0) 1)) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) (+ 0 1)) 1)) 1)
(+ (+ (cc 11 1) (+ (+ (cc 6 0) 1) 1)) 1)
(+ (+ (cc 11 1) (+ (+ 0 1) 1)) 1)
(+ (+ (cc 11 1) (+ 1 1)) 1)
(+ (+ (cc 11 1) 2) 1)
(+ (+ (+ (cc 11 0) (cc (- 11 1) 1)) 2) 1)
(+ (+ (+ (cc 11 0) (cc 10 1)) 2) 1)
※上記の山の2倍くらいのサイズの山になるので省略
(+ (+ (+ (cc 11 0) 1) 2) 1)
(+ (+ (+ 0 1) 2) 1)
(+ (+ 1 2) 1)
(+ 3 1)
4
Q. スペースとステップ数の増加の程度は何か
調べながら考えた。 下記が丁寧に説明してあるので勉強になる。
SICP 孤読書会 - 1.2 手続きとその生成するプロセス (1.2.1 〜 1.2.3) - プログラミング的な何か、あと自転車日本一周とか
スペース
スペースが上記の展開図でいう山のmaxのサイズというのであれば、金額に比例して山のサイズは大きくなるので、スペースの増加はO(n)で増加していくことになる。
ステップ数
上記の展開図でいうところの山ができるかどうかは、求める金額が硬貨の金額を上回っているかによる。 求める金額上回っているのであれば、その分の硬貨の数だけ山ができる。 山ができてしまえば、上記のスペースと同様O(n)でステップ数が増加していく。
ただし、求める金額が硬貨の数を下回るのは求める金額がかなり小さい場合だけなので、Orderとして計算する場合ざっくりとした計算をすればいいので、この際無視する。 なので5枚すべて上回っていると仮定すると、硬貨の数分O(n)になるので、上記の関数の場合のステップ数の増加はO(n^5)で増加していく。