schemeracketcoin-change

Racket Function for Changing 2 and 1 Euro with 10 Cents and 20 Cents


Can somebody explain me a code in Racket in which I change 2 Euro and a 1 Euro Coin with 10 Cents and 20 Cents?

I can only change one time a 2 Euro coin and one time a 1 Euro coin. With 20 Cents and 10 Cents. Here is my code:

(define (change sum coins) 
  (if (< sum 200) 
    0 
    (if (= sum 200) 
      1 
      (if (and (> sum 0) 
               (<= (length coins) 0)) 
        0 
        (+ (change (- sum (car coins)) (cdr coins)) 
           (change sum (cdr coins))))))) 

(change 200'(20 10)) 
(change 100'(20 10)) 

So what I have to modify? Thanks for your help!


Solution

  • Since the 200 target is hardcoded, you should start with the current sum of 0, and count up, not down:

    (define (change sum coins) 
      (if (> sum 200)             ; invalid solution
        0 
        (if (= sum 200)              ; good solution
          1 
          (if (= (length coins) 0)     ; no more coins to use
            0 
            (+ (change (+ sum (car coins))  ; use first coin,
                       coins)               ; _increasing_ the sum
               (change sum 
                       (cdr coins)))))))      ; don't use first coin any more
    

    Now we have

    > (change 0 '(10))
    1
    > (change 0 '(20 10))
    11
    > (change 0 '(7))
    0
    > 
    

    Now you can abstract away the target value of 200, making it a parameter in a new function which will have to make this function its inner definition so it has access to its parameter:

    (define (coin-change-ways target coins)
      (define (change sum coins) 
         ....
         ....)
      (change 0 coins))
    

    See this for more explanations.