「プロジェクトオイラー問53」の編集履歴(バックアップ)一覧はこちら
「プロジェクトオイラー問53」(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万以上になったら100万に切りそろえて、それ以後100万という記号として扱えば
int型しかない言語でもこの問題は解けます。
Prologなので桁数は関係ありませんが心理的な理由です。
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).
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万以上になったら100万に切りそろえて、それ以後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).