problem 31

Problem 31 - Project Euler

金額が 1, 2, 5, 10, 20, 50, 100, 200 のコインがあるときに 200 の作り方は何通りあるかという問題です。

(use srfi-1)

(define kinds (list 200 100 50 20 10 5 2 1))

; k 以下のコインを使って n を作る方法は何通りあるか（ k のコインは最低一枚以上は使う）
(define (f k n)
  (let ((found (member k kinds))) 
    (cond ((= k 1) 1)
          (found (let ((k1 (car found))                  ; k1 = k
                       (k2 (cadr found)))                ; k1 の次のコイン
                   (fold (lambda (x p)                  
                           ; k1 を x 枚使ったため残りの金額を k2 以下のコインで組みあわせる
                           (+ (F k2 (- n (* k1 x))) p)) 
                         0
                         (iota (quotient n k1) 1))))     ; k1 は 1 〜 n/k1 枚使える
          (else 0))))                                    ; k のコインがない場合はエラー

; k 以下のコインを使って n を作る方法は何通りあるか(使用コインの制限なし)
(define (F k n)
  (fold (lambda (x p) (+ (f x n) p)) 0 (member k kinds)))

(define (p31) (F 200 200))

(print (p31))