「prolog勉強プロジェクトオイラー141～150」の編集履歴（バックアップ）一覧に戻る
プロジェクトオイラーの問題を堀江伸一さんがProlog言語で特ページ。
整数論の知識はないので早いコードはあまりかけない。
*Problem 145 「10億未満に存在するreversibleな数はいくつか?」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20145
ある正の整数nについて, [n + reverse(n)]が奇数のみで表されるようなnが存在する. 例えば, 36 + 63 = 99, 409 + 904 = 1313 のように. この性質を持つ数を, reversibleと呼ぶことにする. つまり, 36, 63, 409, 904はrevesibleである. 先頭の0はnでもreverse(n)でも許されない.
1000未満には120個のreversibleな数が存在する.
10億(10^9)未満では, いくつのreversibleな数が存在するか.
小学生でもわかる考え方で考えてみます。
動的計画法で数字を末尾から確定していきます。
-何桁の数字を計算しようとするか、
-何桁目の処理か、
-前の桁が奇数だったか偶数だったか、
-繰り上がりはあったかなかったか。
この4種類のデータを変数として漸化式を適用すれば10＾100くらいは一瞬でもとまります。
実際一瞬で答えが出てそれぞれ下記の通りとなりました。
10＾9で正しい答えが出ているので下の答えもたぶん正しいとは思いますがどなたかどうぞ。
10^20 413497007808720
10^30 9897363562297007808720
10^50 5843418646273505631953562297007808720
10^100 49510212020123267770652667541980512749637205445373505631953562297007808720
Prolog Code
sum([],0):-!.
sum([[_,_,C]|Rest],Result):-sum(Rest,Re),Result is Re+C.
union_sum([],Set,[Set]):-!.
union_sum([[P,U,C]|Rest],[P,U,C1],Result):-
!,
C2 is C+C1,
union_sum(Rest,[P,U,C2],Result).
union_sum([A|Rest],Set,[Set|Result]):-
union_sum(Rest,A,Result).
% KiAdd0 30
% ki Add1 20
% gu Add0 25
% gu Add1 25
next_calc([0,1,C],[0,1,C1]):-!,C1 is C*25.
next_calc([0,0,C],[1,1,C1]):-!,C1 is C*20.
next_calc([1,1,C],[0,0,C1]):-!,C1 is C*25.
next_calc([1,0,C],[1,0,C1]):-!,C1 is C*30.
next_calc_w(Memo,Result):-
member(M,Memo),
next_calc(M,Result).
last1([1,1,C],[0,0,C1]):-!,C1 is C*5.
last1([0,1,C],[0,1,C1]):-!,C1 is C*5.
last0([0,1,C],[0,1,C1]):-!,C1 is C*25.
last0([1,0,C],[0,0,C1]):-!,C1 is C*30.
seed([1,U,1]):-
between(1,9,A),
between(1,9,B),
1 =:= (A+B) mod 2,
(A+B<10->U is 0;U is 1).
calc(2,_,_,[0,0,20]):-!.
calc(Len,KetaP,Memo,Result):-
1=:=Len mod 2,
(Len-1)//2=<KetaP,
!,
member(M,Memo),
last1(M,Result).
calc(Len,KetaP,Memo,Result):-
0=:=Len mod 2,
(Len-1)//2=<KetaP,
!,
member(M,Memo),
last0(M,Result).
calc(Len,KetaP,Memo,Result):-
!,
findall(M,next_calc_w(Memo,M),Memo1),
msort(Memo1,Memo2),
[Top|Memo3]=Memo2,
union_sum(Memo3,Top,Memo4),
KetaP1 is KetaP+1,
calc(Len,KetaP1,Memo4,Result).
seed_create(Result):-
findall(Seed,seed(Seed),Seeds),
msort(Seeds,Seeds1),
[Top|Seeds2]=Seeds1,
union_sum(Seeds2,Top,Result).
calc_start(Seed,Sum):-
between(2,100,N),
calc(N,1,Seed,Sum).
main145:-seed_create(Seed),
findall(Sum,calc_start(Seed,Sum),Sums),
sum(Sums,Ans),write([a,Ans]).
*Problem 147 「斜交平行格子内の長方形」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20147
長方形の中に線が描かれており何個の長方形が隠れているか答える問題。
とりあえずｎ*ｍサイズでｈ=<wのときのみ正しい答えをだす関数を動的計画法で作りまあまあの速度で正答。
最初全探索する遅いコードで正答。
他人のコードをチラ見するもなんだか漸化式を使った方法で見当がつかなかったので動的計画法となりました。
カンニングするのもなんだし動的計画法でもう少し攻めて、それが十分早くなってから他人の漸化式を理解するところに行きたいと思う。
たぶん動的計画法を極めた先に漸化式があると思われます。
現状あるサイズを計算するときはまあまあ効率的になってるけど、別のサイズを計算するときと計算がかぶってて同じ計算をしている。
ここを改善すれば速度は出るはず。
sum([],0):-!.
sum([P|Rest],Result):-sum(Rest,Re),Result is Re+P.
sum_up1([],P1,Sum,Result):-!,Result is Sum+P1.
sum_up1([P|Rest],P1,Sum,Result):-
(P<P1->Sum1 is Sum+P;Sum1 is Sum+P1),
sum_up1(Rest,P1,Sum1,Result).
sum_up(_,[],Sum,Sum):-!.
sum_up(Left,[[_,_,P]|Right],Sum,Result):-
sum_up1(Left,P,Sum,Sum1),
sum_up([P|Left],Right,Sum1,Result).
in_area(X,Y,H,W):-
(1-(Y mod 2))=<X,
X=<(2*(W-1)-((Y+1) mod 2)),
Y=<(H-1)*2,
0=<Y.
seed([0,1,1],H,W):-in_area(0,1,H,W).
seed([1,0,1],H,W):-in_area(1,0,H,W).
next_cell([[X,Y,P]|_],[X1,Y1,P1],H,W):-
X1 is X+1,
Y1 is Y+1,
P1 is P+1,
in_area(X1,Y1,H,W).
next_cell([[X,Y,_]],[X1,Y1,1],H,W):-
X1 is X+2,
Y1 is Y,
in_area(X1,Y1,H,W).
next_cell([_|Cells],Result,H,W):-
next_cell(Cells,Result,H,W).
top_add([],[],_,_):-!.
top_add([[X,Y,1]],[[X1,Y1,1]],H,W):-
X1 is X,Y1 is Y+2,
in_area(X1,Y1,H,W),!.
top_add([[X,Y,P]|Rest],[[X1,Y1,1],[X,Y,P]|Rest],H,W):-
X1 is X-1,Y1 is Y+1,
in_area(X1,Y1,H,W),!.
top_add(A,A,_,_):-!.
calc([],Sum,Sum1,H,W):-!,Sum1 is Sum+(H*(H+1)*W*(W+1))//4.
calc(Cells,Sum,Result,H,W):-
sum_up([],Cells,Sum,Sum1),
findall(Cell,next_cell(Cells,Cell,H,W),Cells1),
top_add(Cells1,Cells2,H,W),
calc(Cells2,Sum1,Result,H,W).
test(Result1):-
between(1,43,H),
between(H,47,W),
findall(Cell,seed(Cell,H,W),Cells),
calc(Cells,0,Result,H,W),
write([H,W,Result]),nl,
((H=:=W;43<W)->Result1 is Result;Result1 is Result*2).
main147:-findall(X,test(X),Xs),
sum(Xs,Ans),write(Ans).
