「プロジェクトオイラー問５３」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問５３ - (2014/02/18 (火) 14:33:12) のソース

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