Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|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を作る方法は何通りあるか?

```scheme

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

```