Hatena::Groupcsnagoya-sicp

gabuchanの日記

2008-11-10

問題1.14

| 15:28

木構造のイメージでも作ろうかと思ったけど面倒なのでダラダラ出力させてみた。

(define (count-change amount)
  (cc amount 5 0))

(define (cc amount kinds-of-coins space)
  (print #`",(make-string space #\\-)(cc ,amount ,kinds-of-coins)")
  (cond [(= amount 0) 1]
        [(or (< amount 0) (= kinds-of-coins 0)) 0]
        [else (+ (cc amount
                     (- kinds-of-coins 1)
                     (+ space 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins
                     (+ space 1)))]))

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

(count-change 11)
$ gosh 1.14.scm
(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)

問われているスペースとステップ数の増加の程度は後で書く。