(wat-aro)

無職から有職者にランクアップしました

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