2.19

练习 2.19 请考虑1.2.2节的兑换零钱方式计数程序。如果能够轻而易举地改变程序里所用的兑换币种就更好了。譬如说，那样我们就能计算出1英镑的不同兑换方式的数目。在写前面那个程序时，有关币种的知识中有一部分出现在过程 first-denomination 里，另一部分出现在过程 count-change （它知道有5种U.S.硬币）。如果能够用一个表来提供可用于兑换的硬币就更好了。

我们希望重写出过程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给出的回答吗？为什么？

表结构的基本操作

• list-ref
• length
• append

first-denomination

(define first-denomination car)
(first-denomination (list 1 2 3 4))

except-first-denomination

(define except-first-denomination cdr)
(except-first-denomination (list 1 2 3 4))

no-more?

(define no-more? null?)
(no-more? (list))

重写后的 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)))))

us-coins

(cc 100 us-coins)

验证一下 coin-values 的排列顺序对结果的影响：

(define (append list1 list2)
  (if (null? list1)
    list2
    (cons (car list1) (append (cdr list1) list2)))
)

(define (reverse lst) 
  (if (null? (cdr lst))
      lst
      (append (reverse (cdr lst)) (list (car lst)))))

(cc 100 (reverse us-coins))

看起来排列顺序不会影响计算结果，因为加减法的结合次序不影响结果。