SICP 問題 2.19
(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 first-denomination car) (define except-first-denomination cdr) (define no-more? null?)
coins-valueの順番は答えに関係ない.
list内のすべての組み合わせを行っているためである.
ただし,降順にしたほうが繰り返しが少なくなるため効率がよくなる.
gosh> (define us-coins (list 50 25 10 5 1)) us-coins gosh> (cc 100 us-coins) 292 gosh> (cc 100 (list 25 50 10 5 1)) 292 gosh> (cc 100 (list 25 10 5 1 50)) 292 gosh> (cc 51 (list 25 10 5 1 50)) 50 gosh> (cc 51 us-coins) 50