Solution to Exercise 1.14. Draw the tree illustrating the process generated by the count-change procedure of section 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?
The tree illustration can be as given below. The order of value of coins have been reversed inorder to reduce the size of the diagram. As said in the section 1.2.2, order of coins does not matter. So the resultant procedure will be as given below.
(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) 50) ((= kinds-of-coins 2) 25) ((= kinds-of-coins 3) 10) ((= kinds-of-coins 4) 5) ((= kinds-of-coins 5) 1)))
11 => 50 25 10 5 1
4|0
+----------+---------+
| |
11 => 25 10 5 1 -39 => 50 25 10 5 1
4|0
+--------+-------+
| |
11 => 10 5 1 -14 => 25 10 5 1
3|1
+-------+--------------------------------------+
| |
11 => 5 1 1=> 10 5 1
1|2 1|0
+-------+-------+ +----+---------+
| | | |
11=> 1 6 => 5 1 1=> 5 1 -9 => 10 5 1
1|1 1|0
+--------+----+ +-----+---+
| | | |
6 => 1 1 => 5 1 1 => 1 -4=> 5 1
1|0
+----+----+
| |
1 => 1 -4=> 5 1
<< Previous exercise (1.13) | sicp-solutions | Next exercise (1.15) >>