sicp-ex-2.19


jz

  
 ;; Counting change. 
  
 ;; Helper methods, could define them in cc too: 
 (define (first-denomination denominations) (car denominations)) 
 (define (except-first-denom denominations) (cdr denominations)) 
 (define (no-more? denominations) (null? denominations)) 
  
 (define (cc amount denominations) 
   (cond  
    ;; If there's no change left, we have a solution 
    ((= amount 0) 1) 
     
    ;; If we're gone -ve amount, or there are no more kinds of coins 
    ;; to play with, we don't have a solution. 
    ((or (< amount 0) (no-more? denominations)) 0) 
     
    (else 
     ;; number of ways to make change without the current coin type 
     ;; plus the number of ways after subtracting the amount of the 
     ;; current coin. 
     (+ (cc amount (except-first-denom denominations)) 
        (cc (- amount  
               (first-denomination denominations))  
            denominations))))) 
  
  
 (cc 100 (list 50 25 10 5 1)) 
 ;; 292 
  
 (cc 100 (list 100 50 20 10 5 2 1 0.5)) 
 ;; 104561 ... wow. 
  

atrika

this also works

  
 (define no-more? null?) 
 (define except-first-denomination cdr) 
 (define first-denomination car) 
  

>>>

Rptx

For the last part of the exercise. The order of the coins does not affect the result. Becuase the procedure computes all possible combinations. But it does affect the speed of the computation. If you start with the lower valued coins, it'll take much longer.

  
 (define (timed-cc amount coin-values start-time) 
   (cc amount coin-values) 
   (- (runtime) start-time)) 
 (timed-cc 200 us-coins (runtime))       ;.6799 
 (timed-cc 200 (reverse us-coins) (runtime)) ;1.27 
  
 (if (> (timed-cc 100 (reverse us-coins) (runtime)) 
        (timed-cc 100 us-coins (runtime))) 
     (display "Reverse takes longer") 
     (display "Reverse does not take longer")) ;As expected, reverse takes longer