計算機プログラムの構造と解釈

1.14

;木構造を描く
(cc 11 5) -> 4
-(cc 11 4) -> 4
--(cc 11 3) -> 4
---(cc 11 2) -> 3
----(cc 11 1) -> 1
-----(cc 11 0) -> 0
------0
-----(cc 10 1) -> 1
------(cc 10 0) -> 0
-------0
------(cc 9 1) -> 1
-------(cc 9 0) -> 0
--------0
-------(cc 8 1) -> 1
--------(cc 8 0) -> 0
---------0
--------(cc 7 1) -> 1
---------(cc 7 0) -> 0
----------0
---------(cc 6 1) -> 1
----------(cc 6 0) -> 0
-----------0
----------(cc 5 1) -> 1
-----------(cc 5 0) -> 0
------------0
-----------(cc 4 1) -> 1
------------(cc 4 0) -> 0
-------------0
------------(cc 3 1) -> 1
-------------(cc 3 0) -> 0
--------------0
-------------(cc 2 1) -> 1
--------------(cc 2 0) -> 0
---------------0
--------------(cc 1 1) -> 1
---------------(cc 1 0) -> 0
----------------0
---------------(cc 0 1) -> 1
----------------(cc 0 0) -> 0
-----------------0
----------------(cc -1 1) -> 1
-----------------1
----(cc 6 2) -> 2
-----(cc 6 1) -> 1
------(cc 6 0) -> 0
-------0
------(cc 5 1) -> 1
-------(cc 5 0) -> 0
--------0
-------(cc 4 1) -> 1
--------(cc 4 0) -> 0
---------0
--------(cc 3 1) -> 1
---------(cc 3 0) -> 0
----------0
---------(cc 2 1) -> 1
----------(cc 2 0) -> 0
-----------0
----------(cc 1 1) -> 1
-----------(cc 1 0) -> 0
------------0
-----------(cc 0 1) -> 1
------------(cc 0 0) -> 0
-------------0
------------(cc -1 1) -> 1
-------------1
-----(cc 1 2) -> 1
------(cc 1 1) -> 1
-------(cc 1 0) -> 0
--------0
-------(cc 0 1) -> 1
--------(cc 0 0) -> 0
---------0
--------(cc -1 1) -> 1
---------1
------(cc -4 2) -> 0
-------0
---(cc 1 3) -> 1
----(cc 1 2) -> 1
-----(cc 1 1) -> 1
------(cc 1 0) -> 0
-------0
------(cc 0 1) -> 1
-------(cc 0 0) -> 0
--------0
-------(cc -1 1) -> 1
--------1
-----(cc -4 2) -> 0
------0
----(cc -9 3) -> 0
-----0
--(cc -14 4) -> 0
---0
-(cc -39 5) -> 0
--0
;;おそらくこのような感じになるのではないか

;;ccを以下のように書き換えて試してみた。
(define (cc amount kinds-of-coins space)
  (display (string-append space "(cc "(number->string amount) " "
			  (number->string kinds-of-coins) ")"))
  (newline)
  (cond ((= amount 0) 1)
	((or (< amount 0) (= kinds-of-coins 0)) 0)
	(else (+ (cc amount (- kinds-of-coins 1)
		     (string-append space "-"))
		 (cc (- amount (first-denomination kinds-of-coins))
		     kinds-of-coins (string-append space "-"))))))

;実行。
(count-change 11) ->

(cc 11 5)
-(cc 11 4)
--(cc 11 3)
---(cc 11 2)
----(cc 11 1)
-----(cc 11 0)
-----(cc 10 1)
------(cc 10 0)
------(cc 9 1)
-------(cc 9 0)
-------(cc 8 1)
--------(cc 8 0)
--------(cc 7 1)
---------(cc 7 0)
---------(cc 6 1)
----------(cc 6 0)
----------(cc 5 1)
-----------(cc 5 0)
-----------(cc 4 1)
------------(cc 4 0)
------------(cc 3 1)
-------------(cc 3 0)
-------------(cc 2 1)
--------------(cc 2 0)
--------------(cc 1 1)
---------------(cc 1 0)
---------------(cc 0 1)
----(cc 6 2)
-----(cc 6 1)
------(cc 6 0)
------(cc 5 1)
-------(cc 5 0)
-------(cc 4 1)
--------(cc 4 0)
--------(cc 3 1)
---------(cc 3 0)
---------(cc 2 1)
----------(cc 2 0)
----------(cc 1 1)
-----------(cc 1 0)
-----------(cc 0 1)
-----(cc 1 2)
------(cc 1 1)
-------(cc 1 0)
-------(cc 0 1)
------(cc -4 2)
---(cc 1 3)
----(cc 1 2)
-----(cc 1 1)
------(cc 1 0)
------(cc 0 1)
-----(cc -4 2)
----(cc -9 3)
--(cc -14 4)
-(cc -39 5)
4
;ちゃんと見てないが多分あってる。

;増加の程度について。
;スペースとは再帰の深さの値である。
;なので、もっとも長くなるのは全部1セントの場合であり、nとなるはずだが、
;初め5セントからはじめるため、n+4となる
;スペース:θ(n+4)
;ステップ:保留(わからない)