Project Euler で紹介されている問題31を解いてみました。ある金額に対して、指定されたコインを組み合わせて支払う方法が何通りあるか求める問題です。
Project Euler 問題31（コインの合計）
イギリスの通貨は、ポンド（£）とペンス（p）である。一般に流通しているコインは次の8枚である。
1p, 2p, 5p, 10p, 20p, 50p, £1（100p）, £2（200p）
£2（200p）を作るには、次のようにすればよい。
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
コインの枚数を問わないとして、£2は何通り作ることができるか求めよ。
解答例
各コインの枚数をループ変数として表現します。それぞれのコインに対して、0枚から、200p すべてをそのコインで作った枚数まで繰り返します。コインが8種類あるため、8重ループとなります。
次の C プログラムでは、配列 coins にコインの金額を格納しました。ループ変数も配列 no として表現しました。解答は、大きくなる可能性があるため、unsigned long long int 型を使いました。
#include <stdio.h>
typedef unsigned long long int ull;
#define N 200
int main(void)
{
int no[8];
int coins[8] = {1, 2, 5, 10, 20, 50, 100, 200};
int i, sum;
ull count;
count = 0;
for (no[0] = 0; no[0] <= N / coins[0]; ++no[0]) {
for (no[1] = 0; no[1] <= N / coins[1]; ++no[1]) {
for (no[2] = 0; no[2] <= N / coins[2]; ++no[2]) {
for (no[3] = 0; no[3] <= N / coins[3]; ++no[3]) {
for (no[4] = 0; no[4] <= N / coins[4]; ++no[4]) {
for (no[5] = 0; no[5] <= N / coins[5]; ++no[5]) {
for (no[6] = 0; no[6] <= N / coins[6]; ++no[6]) {
for (no[7] = 0; no[7] <= N / coins[7]; ++no[7]) {
sum = 0;
for (i = 0; i < 8; ++i) {
sum += no[i] * coins[i];
}
if (sum == N) {
++count;
}
}
}
}
}
}
}
}
}
printf("Problem031: %lld\n", count);
return 0;
}8重ループを使ったこのプログラムはエレガントとは、とても呼べません。ただし、目的は達成して、正解を出力することができました。
計算量に対しての考察
問題で与えられた 200 を大きくすることを考えましょう。例えば、50倍の £100（10000p）を作る通り数を求めてみましょう。
プログラムの N を 10000 に変更して動かします。プログラムは戻ってきません。解答を出力することもなく、計算を続けているようです。
N を 200 から 10000 にすることで、ひとつのループに対して50倍、8重ループでは、508 倍の計算時間がかかります。これは、約 4 × 1013 となります。計算量が非常に大きくなることが分かりました。
最後に
問題31を素朴な方法で解いてみました。
一方、合計の結果となる数字（この問題の場合、200）を大きくすると、この素朴な方法では、計算量がすぐに大きくなり、解を求めることが難しいことが分かりました。
次回は、別のアルゴリズムを使って、大きな数字に対しても解ける方法を紹介します。
