Consider the change-counting program of section 1.2.2. It would be nice to be able to easily change the currency used by the program, so that we could compute the number of ways to change a British pound, for example. As the program is written, the knowledge of the currency is distributed partly into the procedure
first-denomination
and partly into the procedure count-change
(which knows that there are five kinds of U.S. coins). It would be nicer to be able to supply a list of coins to be used for making change.
We want to rewrite the procedure
cc
so that its second argument is a list of the values of the coins to use rather than an integer specifying which coins to use. We could then have lists that defined each kind of currency:(define us-coins (list 50 25 10 5 1)) (define uk-coins (list 100 50 20 10 5 2 1 0.5))
We could then call
cc
as follows:> (cc 100 us-coins) 292
To do this will require changing the program
cc
somewhat. It will still have the same form, but it will access its second argument differently, as follows:(define (cc amount coin-values) (cond ((= amount 0) 1) ((or (< amount 0) (no-more? coin-values)) 0) (else (+ (cc amount (except-first-denomination coin-values)) (cc (- amount (first-denomination coin-values)) coin-values)))))
Define the procedures
first-denomination
, except-first-denomination
, and no-more?
in terms of primitive operations on list structures. Does the order of the list coin-values
affect the answer produced by cc
? Why or why not? The exercise already tells us the representation we're going to be using for denominations: lists of the denomination values. As a result, the procedures
first-denomination
, except-first-denomination
, and no-more?
are straightforward to define. first-denomination
just needs to return the car
of the list, except-first-denomination
just needs to return the cdr
of the list, and no-more?
just needs to check to see if the list is empty:
(define (first-denomination coin-values) (car coin-values)) (define (except-first-denomination coin-values) (cdr coin-values)) (define (no-more? coin-values) (null? coin-values))We can check this works as expected:
> (cc 100 us-coins) 292 > (cc 100 uk-coins) 104561As for whether or not the order of the list
coin-values
affects the answer produced by cc
, we can easily test this:
> (cc 100 (list 1 5 10 25 50)) 292 > (cc 100 (list 5 25 50 10 1)) 292So no, it doesn't appear as if it does affect ordering. So why not? Well, looking at the algorithm we can see that each non-terminal call to
cc
sums the results of two (also potentially non-terminal) recursive calls:
- One of these finds the number of ways we can change
amount
using denominations other than the first one in the list of denominations. As a result, this counts all of the combinations for changingamount
that do not use the first denomination. - The other deducts the value of the first denomination in the list of denominations from
amount
and finds how many ways we can change that using any and all of the denominations in the list. As a result, this counts all of the combinations for changingamount
that do use the first denomination.
amount
. As a result the order of the denominations does not matter.
No comments:
Post a Comment