Exercise 2.19 · 习题

Exercise 2.19: Consider the change-counting
program of 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?

练习 2.19：考虑 1.2.2 节的找零程序。若能方便地改变程序所用的货币，使我们能计算兑换一英镑的方法数，那就好了。在现有程序中，货币的信息分散在过程 first-denomination 和过程 count-change 中（后者知道有五种美国硬币）。若能提供一张硬币面额表来进行兑换，将更为方便。

我们希望重写过程 cc，使其第二个参数是一个包含所用硬币面额的表，而不是指定使用哪种硬币的整数。这样我们就能有定义各种货币的表：

(define us-coins
(list 50 25 10 5 1))

(define uk-coins
(list 100 50 20 10 5 2 1 0.5))

然后可以如下调用 cc：

(cc 100 us-coins)
292

为此需要对 cc 做一些修改。它的形式不变，但访问第二个参数的方式有所不同：

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

用表结构的基本操作定义过程 first-denomination、except-first-denomination 和 no-more?。表 coin-values 的顺序是否影响 cc 产生的结果？为什么？