ホーム - Project Euler

Problem 31¶

Coin Sums¶

In the United Kingdom the currency is made up of pound (£) and pence (p). There are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

硬貨の和¶

イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である.

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

以下の方法で£2を作ることが可能である．

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

これらの硬貨を使って£2を作る方法は何通りあるか?

(import (scheme base)
        (gauche base))

(define (coin-pattern n lis)
  (cond
    [(zero? n) 1]
    [(negative? n) 0]
    [(null? lis) 0]
    [else
      (+ (coin-pattern n (cdr lis))
         (coin-pattern (- n (car lis))
                       lis))]))

(define answer-31
  (coin-pattern 200 '(200 100 50 20 10 5 2 1)))

(format #t "31: ~d~%" answer-31)