Original

In England the currency is made up of pound, £, and pence, p, and 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 + 150p + 220p + 15p + 12p + 31p
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ポンドを作る方法はいくつあるか?

当てにならないソースコード(C#)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
using System;
using System.Collections.Generic;

namespace ProjectEuler {
    class Problem31 : Problem{
        List<int> Coins = new List<int>{1, 2, 5, 10, 20, 50, 100, 200};
        public Problem31() {
            Console.WriteLine("> " + Pettern(200, Coins.Count-1));
        }

        long Pettern(int target, int kind) {
            if (target == 0) {
                return 1;
            }
            long petterns = 0;
            for (int i = 0,x;i<=200 ; i++) {
                x = i * Coins[kind];
                if (x >= target) {
                    if (x == target)
                        ++petterns;
                    break;
                }
                if (kind > 0) {
                    petterns += Pettern(target - x, kind - 1);
                }
            }
            return petterns;
        }
    }
}


こういうときにこそ再帰ですよね。