prolog勉強プロジェクトオイラー51～60 の編集履歴一覧 - c21coterie @ ウィキ

「prolog勉強プロジェクトオイラー51～60」の編集履歴（バックアップ）一覧に戻る

prolog勉強プロジェクトオイラー51～60 - (2013/08/06 (火) 12:14:33) の編集履歴(バックアップ)

プロジェクトオイラーの問題を堀江伸一が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へ調べていきます。
ある数になった時そのあと何回以内で計算が終わるか、計算が終わらないか配列にメモっておけば５０回以内で計算が終わるかのチェックで少しだけ計算量を下げることが出来ます。
そこまでしなくてもすぐに答えが出るので気にしませんでした。

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

√２の連分数展開を一項ずつ計算していく時、１０００項目までで分子の桁数が分母の桁数を超える回数を答えよ。
計算速度を稼ぐために前の項の計算結果を再利用するくらいで特に工夫はしてません。

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

うーん？
この問題はまずグラフとして見る？
次に集合の問題に翻訳する。
まずグラフとして見て、素数を点、結合可能なものを片側矢印で繋げる。
上限を設けて少しずつ先に延ばす戦略が有効。
100万までの素数を２つに分解して素数なら、その点を繋げ両方がつながれば両側やじるしとする。
次にグラフを、その点の素数と両側で結合可能な素数のリストのリストA0～Anと見る。
リストの要素が５つ以上あるものだけを選別しB0～Bｍまでとする。
次にB0～Bmまでの直積をとる。
取り方は素数の共通集合で５つ以上残るものだけを残しC0～Cｋとする。
これを計4回繰り返して残ったリストのうち最小要素5つを取ったものが答えとなる。
n>=mなのでリストの数はどんどん減っていくから計算量はそれほど増大しない。

c21coterie @ ウィキ