Project Euler 31

イギリスでは硬貨はポンド£とペンス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ポンドを作る方法は何通りあるか?

Mathematica

A = Table[0, {i, 200}];

Do[
 For[j = i, j <= 200, j++,
  If[j == i,
   A[[j]] += 1,
   A[[j]] += A[[j - i]]
   ]
  ]
 , {i, {1, 2, 5, 10, 20, 50, 100, 200}}]

A[[200]]

漸化式的な考えです。
Aは200個の配列で、それぞれの配列番号ペンスを作る組み合わせは何通りあるか、を示しています。
Aの100番目には100ペンスになる組み合わせが入っています。

C/C++

#include <iostream>
using namespace std;

int is200(int p1,int p2,int p5,int p10,int p20,int p50,int p100,int p200){
	int p;
	p = p1*1 + p2*2 + p5*5 + p10*10 + p20*20 + p50*50 + p100*100 + p200*200;
	if(p>200) return 1;
	else if(p<200) return -1;
	else return 0;
}

int main(){
	int count=0;
	int p1, p2, p5, p10, p20, p50, p100, p200;

	for(p200=0 ; p200<=1 ; p200++){
		if(is200(0,0,0,0,0,0,0,p200)==1) break;
		for(p100=0 ; p100<=2 ; p100++){
			if(is200(0,0,0,0,0,0,p100,p200)==1) break;
			for(p50=0 ; p50<=4 ; p50++){
				if(is200(0,0,0,0,0,p50,p100,p200)==1) break;
				for(p20=0 ; p20<=10 ; p20++){
					if(is200(0,0,0,0,p20,p50,p100,p200)==1) break;
					for(p10=0 ; p10<=20 ; p10++){
						if(is200(0,0,0,p10,p20,p50,p100,p200)==1) break;
						for(p5=0 ; p5<=40 ; p5++){
							if(is200(0,0,p5,p10,p20,p50,p100,p200)==1) break;
							for(p2=0 ; p2<=100 ; p2++){
								if(is200(0,p2,p5,p10,p20,p50,p100,p200)==1) break;
								for(p1=0 ; p1<=200 ; p1++){
									if(is200(p1,p2,p5,p10,p20,p50,p100,p200)==0) count++;
								}
							}
						}
					}
				}
			}
		}
	}

	cout << count << endl;

	int end;
	cin >> end;
}

ザ・愚直。