练习 2.19

以下是找零程序的其他函数:

;;; 19-other.scm

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

再加上练习给出的 cc 程序:

;;; 19-cc.scm

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

现在可以进行找零测试了:

1 ]=> (load "19-cc.scm")

;Loading "19-cc.scm"... done
;Value: cc

1 ]=> (load "19-other.scm")

;Loading "19-other.scm"... done
;Value: no-more?

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

;Value: us-coins

1 ]=> (cc 100 us-coins)

;Value: 292

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

;Value: uk-coins

1 ]=> (cc 100 uk-coins)

;Value: 104561

金币的排序并不会影响找零的结果,验证这一断言的最简单方法就是将一个逆序的金币列表重新传入 cc 程序,可以看到计算的结果和之前未逆序的金币排列一样:

1 ]=> (cc 100 (reverse us-coins))

;Value: 292

1 ]=> (cc 100 (reverse uk-coins))

;Value: 104561

讨论

blog comments powered by Disqus