プロジェクトオイラー問５３ - c21coterie @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2053

Problem 53 「組み合わせ選択」 †

12345から3つ選ぶ選び方は10通りである.

123, 124, 125, 134, 135, 145, 234, 235, 245, 345.
組み合わせでは, 以下の記法を用いてこのことを表す: 5C3 = 10.

一般に, r ≤ n について nCr = n!/(r!(n-r)!) である. ここで, n! = n×(n−1)×...×3×2×1, 0! = 1 と階乗を定義する.

n = 23 になるまで, これらの値が100万を超えることはない: 23C10 = 1144066.

1 ≤ n ≤ 100 について, 100万を超える nCr は何通りあるか?

解法
一段ずつ計算しても十分間に合います。
100万以上になったら１００万に切りそろえて、それ以後１００万という記号として扱えば
int型しかない言語でもこの問題は解けます。
今回もPrologで書いたので桁数は関係ありませんがわかりやすいという理由で100万を記号代わりに扱っています。

add(X,Y,Z):-
	X+Y>=1000*1000,
	!,
	Z is 1000*1000.
add(X,Y,Z):-
	Z is X+Y.

calc_next([1],[],[1]):-!.
calc_next([X|Xs],[Y|Ys],[Z|Zs]):-
	!,
	add(X,Y,Z),
	calc_next(Xs,Ys,Zs).

countM([],0):-!.
countM([1000000|Xs],Count1):-
	!,
 	countM(Xs,Count),
	Count1 is Count+1.
countM([_|Xs],Count):-
	countM(Xs,Count).

calc(101,_,Count):-
	!,
	write(Count).
calc(R,Row,Count):-
	[_|Rest]=Row,
	calc_next(Row,Rest,Row1),
	Row2=[1|Row1],
 	countM(Row2,Add),
	R1 is R+1,
	Count1 is Count+Add,
	calc(R1,Row2,Count1).
main54:-
	calc(1,[1],0).