*問い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).
