0

I'm currently writing a program in scheme (drracket) which is supposed to take a natural number and a list of naturals and give out the number of possibilities for n to be displayed with elements from the list.

For example (p-o-o 37 (list 1 10 100)) is 4 because there are the 4 following possibilities to display it: 1*37; 10*1+1*27; 10*2+1*17; 10*3+7

My problem is that I don't really know how to start since it appears to me that I have to write a program which solves equations for a unknown variable.

Joshua Taylor
  • 84,998
  • 9
  • 154
  • 353
Hubter
  • 43
  • 1
  • 1
  • 3
  • 1
    This is very similar to the "making change" problem of "how many ways can you make N cents given coins in a given denomination". This formulation just allows the denominations to be specified at run time. That doesn't *answer* the question, but it may help you search for it more productively. – Joshua Taylor Jan 08 '15 at 14:01
  • It may be more helpful if you think of the solutions not as `1*37`, `10*1 + 1*27`, etc., but as `100*0 + 10*0 + 1*37`, `100*0 + 10*1 + 1*27`, etc. And while there may be a direct solution to find how many there are, a simple solution would be to generate those combinations and count them. – Joshua Taylor Jan 08 '15 at 14:04
  • 2
    Have a look at [SICP example: Counting change, cannot understand](http://stackoverflow.com/q/27803152/1281433). – Joshua Taylor Jan 08 '15 at 14:04
  • It's the same and SICP later has the exercise 2.19 to change to the same interface – jeffruan Jan 08 '15 at 22:30

1 Answers1

1
;; exercise 2.19                                                                                                                                              
#lang racket/base                                                                                                                                             

(define (cc amount coin-values)                                                                                                                               
  (define no-more? null?)                                                                                                                                     
  (define except-first-denomination cdr)                                                                                                                      
  (define first-denomination car)                                                                                                                             
  (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)))))                                                                                                                                   

racket@ex-2.19.rkt> (cc 37 '(1 10 100))                                                                                                                       
4
jeffruan
  • 294
  • 1
  • 5