プロジェクトオイラーの問題を堀江伸一がPrologで解くページ。 *問い51 http://projecteuler.net/problem=51 Prologには破壊的代入もなければ配列もstd::mapすらない。 リストで擬似的な11分木を構築して解いてみたけれど何か速度が出ない。 計算量の問題なのか、木を分解したり結合しなおしたりする作業が悪いのか? こんな込み入ったことをするくらいなら単純な全部検証の方が早いとは思う。 まあリストで木構造を作ったらどの程度の速度が出るのか実験してみたかったというのが今回のコードです。 単純に全検証の方が早いよな絶対。 nums([a,0,1,2,3,4,5,6,7,8,9]). notPrime(N):-N<2,!. notPrime(N):- sqrt(N,N1), N2 is floor(N1), between(2,N2,N3), 0=:=N mod N3, !. isPrime(N):-not(notPrime(N)). add_a(X,[N|X]):-nums(A), member(N,A). add_list(List,[Y,X]):- nums(A), member(X,List), member(Y,A). create_tree(6,[0,0]):-!. create_tree(N,Result):- N1 is N+1, findall(L,create_tree(N1,L),Re), findall(L,add_list(Re,L),Result). tree_add(_,M,[X,Y],[Re,Y1]):- integer(X), integer(Y), !, Y1 is Y+1, ((X=:=0;M<X)-> Re is M; Re is X). tree_add([],M,[[0,Rest]|Rest1],[[0,Result]|Rest1]):- !, tree_add([],M,Rest,Result). tree_add([N|NumRest],M,[[N,Rest]|Rest1],[[N,Result]|Rest1]):- !, tree_add(NumRest,M,Rest,Result). tree_add(NumList,M,[[N,Rest]|Rest1],[[N,Rest]|Result]):- tree_add(NumList,M,Rest1,Result). num_to_list(0,_,[]):-!. num_to_list(N,R,[a|Result]):- R =:= N mod 10, N1 is N//10, num_to_list(N1,R,Result). num_to_list(N,R,[M|Result]):- M is N mod 10, N1 is N//10, num_to_list(N1,R,Result). check(List):-member(a,List),!. perms(N,Result):- between(0,9,R), num_to_list(N,R,Result), check(Result). tree_adds(N,[],Tree):-!,search(N,Tree). tree_adds(N,[L|List],Tree):- N1 is N-1, tree_add(L,N1,Tree,NextTree), !, tree_adds(N,List,NextTree). tree_search([X,8]):- integer(X), !, write([X,8]). tree_search([[_,Rest]|Rest1]):- member(X,[Rest,Rest1]), tree_search(X). search(1000000,Tree):-!,tree_search(Tree). search(N,Tree):- notPrime(N), !, N1 is N+1, search(N1,Tree). search(N,Tree):- findall(L,perms(N,L),List), N1 is N+1, !, tree_adds(N1,List,Tree). main51:-create_tree(0,Tree),search(1,Tree). *問い52 この問題は1/7の割り算を行ったとき循環するまでに1/7,2/7,3/7,4/7,5/7,6/7という割り算が一度ずつ出てきてそれらは循環している。 だから1/7の循環節が一番小さな数字で答えとなる。 問題はこの数字が最小のものであるか? これを証明しなくてはいけないが特に思いつかないので、結局いつも通り力技となりました num_to_list(0,[]):-!. num_to_list(N,[X|Result]):- X is N mod 10, N1 is N//10, num_to_list(N1,Result). eq_list([],[]):-!. eq_list([X|Rest],List):-select(X,List,Rest1),eq_list(Rest,Rest1). set(10,16). set(100,166). set(1000,1666). set(10000,16666). set(100000,166666). check(N):- num_to_list(N,List), between(2,6,R), N1 is N*R, num_to_list(N1,List2), ( eq_list(List,List2)-> fail;!). main52:- set(A,B), between(A,B,N), not(check(N)), !, write(N). *問い53 そのまま計算して数えるだけ。 next_calc([1],[1]):-!. next_calc([X,Y|Rest],[Z|Result]):- Z1 is X+Y, (1000000=<Z1 -> Z is 1000000;Z is Z1), next_calc([Y|Rest],Result). count100m([],0):-!. count100m([X|Rest],Result):- 1000000=<X,!,count100m(Rest,Re), Result is Re+1. count100m([_|Rest],Result):-count100m(Rest,Result). calc(100,_,Ans):-!, write(Ans). calc(N,List,Ans):- N1 is N+1, next_calc(List,NextList), count100m(NextList,Re), Ans1 is Ans + Re, calc(N1,[1|NextList],Ans1). main53:-calc(0,[1],0). *問い54 http://sozorogusa.blogspot.jp/2012/09/project-euler-problem-54.html この問題についてはリンク先のようにハッカーぽく書けるか、私のように素朴な低レベルコードになるかの差が出る。 ポーカーの役判定をできるだけ短く書けという問題。 これを自力でやらせてみるというのはハッカーとしてのレベルの高さを測るちょうどいいリトマス試験紙かも。 ただいまコード準備中 *問い55 この計算必ず単調増加します。 配列があれば10000~1へ調べていきます。 ある数になった時そのあと何回以内で計算が終わるか、計算が終わらないか配列にメモっておけば50回以内で計算が終わるかのチェックで少しだけ計算量を下げることが出来ます。 そこまでしなくてもすぐに答えが出るので気にしませんでした。 rev_num(0,Sum,Sum):-!. rev_num(N,Sum,Result):- Sum1 is Sum *10+ (N mod 10), N1 is N //10, rev_num(N1,Sum1,Result). calc(50,_):-!. calc(T,N):- rev_num(N,0,N1), T1 is T+1, N2 is N+N1, rev_num(N2,0,N3), (N2=:=N3-> !,fail; calc(T1,N2)). search(N):- between(1,10000,N), calc(0,N). main55:-findall(N,search(N),List),length(List,Len),write(Len). *問い56 そのまま計算するだけ。 keta_sum(0,0):-!. keta_sum(N,Result):- N1 is N//10, M is N mod 10, keta_sum(N1,Re), Result is Re+M. all_perm([Sum,A,B]):- between(1,99,A), between(1,99,B), P is A^B, keta_sum(P,Sum). main56:-findall(L,all_perm(L),List),sort(List,List1),write(List1). *問い57 √2の連分数展開を一項ずつ計算していく時、1000項目までで分子の桁数が分母の桁数を超える回数を答えよ。 計算速度を稼ぐために前の項の計算結果を再利用するくらいで特に工夫はしてません。 gcd(0, B, B). gcd(A, B, G) :- A > 0, R is B mod A, gcd(R, A, G). add(U1,D1,U2,D2,U4,D4):- U3 is U1*D2+U2*D1, D3 is D1*D2, gcd(U3,D3,M), U4 is U3//M, D4 is D3//M. isBig(0,0):-!,fail. isBig(_,0):-!. isBig(U,D):-U1 is U//10,D1 is D//10,isBig(U1,D1). calc(1000,_,_,_,_):-!,fail. calc(_,U,D,U1,D1):- add(U,D,1,1,U1,D1), isBig(U1,D1). calc(N,U,D,U2,D2):- add(U,D,2,1,U1,D1), N1 is N+1, calc(N1,D1,U1,U2,D2). search(U):- calc(0,1,2,U,_). main57:-findall(U,search(U),List),length(List,Len),write(Len). *問い58 この問題はミラーラビン法というものを使うと高速に解けるらしい。 読んだけど一読しただけではよくわからなかったのでいつもの素朴な試し割で素数判定。 遅いけど一応答えは出てるからいいかな(向上心という言葉はないのかな俺?)。 notPrime(N):-N<2,!. notPrime(N):- sqrt(N,N1), N2 is floor(N1), between(2,N2,N3), 0=:=N mod N3, !. isPrime(N):-not(notPrime(N)). search(_,ADD,_,PC,Count):- PC>0, PC1 is PC*10, PC1<Count, !, Ans is ADD-1, write([Ans,PC,Count]). search(N,ADD,[],PC,Count1):- !, ADD1 is ADD+2, search(N,ADD1,[ADD,ADD,ADD,ADD],PC,Count1). search(N,ADD,[A1|Rest],PC,Count):- !, Count1 is Count+1, N1 is N+A1, ( isPrime(N1)-> PC1 is PC+1; PC1 is PC), search(N1,ADD,Rest,PC1,Count1). main58:-search(1,4,[2,2,2,2],0,1). *問い60 うーん? この問題はまずグラフとして見る? 次に集合の問題に翻訳する。 まずグラフとして見て、素数を点とし両側結合可能なものを両側矢印でつなげる。 上限を設けて少しずつ先に延ばす戦略が有効。 例えば10万までの素数の直積を取り、両側結合できるものの点同士を繋げる。 次にグラフを、その点と結合可能な素数を集めたA0~Anと見る(Aiは計算の都合上、その数自信もリストに含めておくと計算が楽になる)。 リストの要素が6つ以上あるものだけを選別しB0~Bmまでとする。 次にB0~Bmまでの直積をとる、Bi、Bjの点の素数pi,pjとしてはpi<pjでなければ計算から除外する。 直積の個々の計算はリスト同士の共通集合で素数リストが6つ以上残るものだけを残しC0~Ckとする。 C0~Ckまでは中身が同じになる場合Ciの点の数字Piは結果がCj=BiBjの計算を行ったときの一番小さなBjの素数点とする。 この直積を取る操作を後3回繰り返して残ったリストのうち最小要素5つの計を答えとすればよい。 これが計算に使用した素数の最大値よりも小さくなればそれが答えである。 答えとならなければ素数の最大値を大きくして上記の計算を再試行すれば良い。 この方法なら計算量はそんなに増大しない。 問題はこれを楽に実装するならC++のstd::mapが便利であり、Prologで効率よく実装するにはちょっとしたアクロバティックな実装が必要となる点である。