計算機プログラムの構造と解釈
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) ;ステップ:保留(わからない)