SICP 練習問題 1.14 （両替の場合計算に関するスペースとステップの問題）

こいつはさっぱりわからん。。
前段の「1.2.3　増加の程度」を読むと、言いたいことはわかるんだが、
じゃあそのΘ(なんちゃら）を求めるには具体的にどうすりゃいいのよ？ってところがわからん。

とりあえず次のようにやってみた。「解答」というレベルではないぞ。。


【問題】
1.2.2節のcount-change手続きが11セントの両替の場合に生成するプロセスを示す木構造を描け。
両替の金額の増加につれ、このプロセスが使うスペースとステップ数の増加の程度は何か。


【なぐりがき解答】
まずはその両替の関数群を記載しよう。

(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)))

上記の関数群中、再帰的に呼び出されているのは「cc」なので、トレースしちゃう。

gosh> (count-change 11)
CALL cc 11 5
  CALL cc 11 4
    CALL cc 11 3
      CALL cc 11 2
        CALL cc 11 1
        RETN cc 1
        CALL cc 6 2
        RETN cc 2
      RETN cc 3
      CALL cc 1 3
        CALL cc 1 2
        RETN cc 1
        CALL cc -9 3
        RETN cc 0
      RETN cc 1
    RETN cc 4
    CALL cc -14 4
    RETN cc 0
  RETN cc 4
  CALL cc -39 5
  RETN cc 0
RETN cc 4
4
gosh> 

木構造を描くのはこれでいんじゃね？頭の中で描いたのはまさにこんな感じのモノ。 次の、「両替の金額の増加につれ、このプロセスが使うスペースとステップ数の増加の程度は何か。」 は、ホントに全くどう考えればいいのか不明っす。 とりあえず、0～99まで渡してみた。

gosh> (use srfi-1) ;iotaを使用したいので。
#
gosh> (map count-change (iota 100))
(1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6 6 6 6 6 9 9 9 9 9 13 13 13 13 13 18 18 18 18 18 24 24 24 24 
24 31 31 31 31 31 39 39 39 39 39 50 50 50 50 50 62 62 62 62 62 77 77 77 77 77 93 93 93 93 93 
112 112 112 112 112 134 134 134 134 134 159 159 159 159 159 187 187 187 187 187 218 218 218 
218 218 252 252 252 252 252)
gosh> 

返却されたリストを５個づつ順番に整理するとこんな感じになった。

1   1   1   1   1
  2   2   2   2   2   
  4   4   4   4   4   
  6   6   6   6   6   
  9   9   9   9   9   
 13  13  13  13  13  
 18  18  18  18  18  
 24  24  24  24  24  
 31  31  31  31  31  
 39  39  39  39  39  
 50  50  50  50  50  
 62  62  62  62  62  
 77  77  77  77  77  
 93  93  93  93  93  
112 112 112 112 112 
134 134 134 134 134 
159 159 159 159 159 
187 187 187 187 187 
218 218 218 218 218 
252 252 252 252 252

でもこれじゃ金額の増加とともに両替の場合の数がどう変化するか、しかわかんねー。
何を元にして考えりゃいいんだろ。。


－