CODEWITHSUNDEEP
schemeracket
Hubter
Hubter

Reputation: 53

Scheme possibilities to order a number with a given list

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.

Upvotes: 0

Views: 89

Answers (1)

jeffruan
jeffruan

Reputation: 294

;; 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)))))                                                                                                                                   

[email protected]> (cc 37 '(1 10 100))                                                                                                                       
4

Upvotes: 1

Related Questions