プロジェクトオイラーの問題を堀江伸一さんがProlog言語で解くページ *Problem 86 「直方体のルート」 † http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2086 この問題は普通に解くと2重ループで簡単に解けるので簡単すぎます、M＝100万までの場合の組み合わせ数を求める発展問題を考えてみました。 int64とintのポカミスがなければ正しい答えが出ているはずです。 流石にM=100万だとPrologではきついのでC++を使用しました。 コード内容 優先順位付きキュー最大使用量1248192 Mの最大が1000000の時の組み合わせ数532281148674 と答えが出ています。 1 基本的な考え方はファレイ数列の性質を利用して原始ピタゴラス数を最小辺が小さな順から取りだす。 それだけで後は組み合わせを計算しているだけです。 コンパイラはBCC C++で6秒で答えが出ます。 #include<stdio.h> #include<queue> #include <algorithm> #include<iostream> struct Fary{ __int64 nl,ml,n,m,nr,mr,minLen,longLen; bool operator<(const Fary& f)const{ if(minLen!=f.minLen)return f.minLen<minLen; if(n!=f.n)return n<f.n; return m<f.m; } void calc_len(){ __int64 a=m*m-n*n; __int64 b=2*m*n; if(a<b){ minLen=a; longLen=b; }else{ minLen=b; longLen=a; } } void set_date(__int64 nl1,__int64 ml1,__int64 n1,__int64 m1,__int64 nr1,__int64 mr1){ nl=nl1; ml=ml1; n=n1; m=m1; nr=nr1; mr=mr1; calc_len(); } Fary createR(){ Fary f; f.nl=n; f.ml=m; f.nr=nr; f.mr=mr; f.n=n+nr; f.m=m+mr; f.calc_len(); return f; } Fary createL(){ Fary f; f.nr=n; f.mr=m; f.nl=nl; f.ml=ml; f.n=nl+n; f.m=ml+m; f.calc_len(); return f; } __int64 calcPerm(__int64 max){ __int64 a,b,ans=0,k,sa,temp; a=minLen; b=longLen; k=max/a; if(a==b){ ans=0; }else if(2*a<b){ ans=0; }else{ sa=(2*a-b); ans=(k*(k+1)*sa)/4-(sa % 2)*((k+1)/4)+k; } std::swap(a,b); k=max/a; temp=(k*(k+1)*b)/4-(b % 2)*((k+1)/4); return temp+ans; } }; int main(){ std::priority_queue<Fary> quF; Fary f,f1; f.set_date(0,1,1,2,1,1); quF.push(f); __int64 ans=0; __int64 m=1; __int64 size1=0; __int64 max=1000*1000; f.set_date(-1,-1,-1,-1,-1,-1); f.minLen=max+1; quF.push(f); for(;m<=max;m++){ while(quF.top().minLen==m){ f=quF.top(); quF.pop(); if((f.m-f.n)%2==1){ ans+=f.calcPerm(max); } f1=f.createR(); if(f1.minLen<=max)quF.push(f1); f1=f.createL(); if(f1.minLen<=max)quF.push(f1); if(quF.size()>size1)size1=quF.size(); } } std::cout<<"優先順位付きキュー最大使用量"<<size1<<"\n"; std::cout<<"Mの最大が"<<m-1<<"の時の組み合わせ数"<<ans; } *問い84 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2084 問い84はみなさんシミュレートで解いてるようです。 この問題をグラフ上の確率分布の収束問題と考えると 今いるマス40*CCマスで出たカードの組2*2*15通り*CHマスででたカードの組み合わせ2＾8*3*7＝12902400点 の確率分布から次の状態を計算して分布の収束結果を考える必要があります。 なので収束の問題と考えると計算量が多くなりすぎますしC++のstd::mapでもギリギリ、Prologのリスト処理では話になりません。 回りを見習って単純にシミュレートすることにしました。 card_ch(0,P,5 ):-35<P,!. card_ch(0,P,35):-25<P,!. card_ch(0,P,25):-15<P,!. card_ch(0,P,15):-5<P ,!. card_ch(0,_, 5):-! . card_ch(1,P,12):-28<P,!. card_ch(1,P,28):-12<P,!. card_ch(1,_,12):- !. card_ch(2,P,P1):-P1 is (P+37) mod 40,!. card_ch(3,_,0):-!. card_ch(4,_,10):-!. card_ch(5,_,11):-!. card_ch(6,_,24):-!. card_ch(7,_,39):-!. card_ch(8,_,5):-!. card_ch(9,P,P):-!. card_cc(0,_,0):-!. card_cc(1,_,10):-!. card_cc(2,P,P):-!. xai(_,_,10,3):-!. xai(P,Sum,P1,K):- !, A is random(4)+1, B is random(4)+1, K1 is K+1, Sum1 is Sum+A+B, (A==B->xai(P,Sum1,P1,K1); P1 is (P+Sum1) mod 40). card_move(P1,P2,CardCH,_,CHP,CCP,CHP1,CCP):- member(P1,[7,22,36]), !, CHP1 is (CHP+1) mod 16, nth0(CHP,CardCH,X), card_ch(X,P1,P2). card_move(P1,P2,_,CardCC,CHP,CCP,CHP,CCP1):- member(P1,[2,17,33]), !, CCP1 is (CCP+1) mod 16, nth0(CCP,CardCC,X), card_cc(X,P1,P2). card_move(30,10,_,_,CHP,CCP,CHP,CCP):-!. card_move(P,P,_,_,CHP,CCP,CHP,CCP):-!. swap([],[]):-!. swap([[X,Y]|Rest],[[Y,X]|Result]):-!, swap(Rest,Result). move(_,2000,_,_,_,_,Count,Result):-!, msort(Count,Result). move(P,Deep,CardCH,CardCC,CHP,CCP,Count,Result):- !, xai(P,0,P1,0), card_move(P1,P2,CardCH,CardCC,CHP,CCP,CHP1,CCP1), Deep1 is Deep+1, select([P2,C],Count,Count1), !, C1 is C+1, move(P2,Deep1,CardCH,CardCC,CHP1,CCP1,[[P2,C1]|Count1],Result). counts([N,0]):- between(0,39,N). card_shuffle([],[]):-!. card_shuffle(Cards,[X|Result]):- length(Cards,Len), P is random(Len), nth0(P,Cards,X), select(X,Cards,Cards1), !, card_shuffle(Cards1,Result). test(Count,1000,_,_):-!,swap(Count,Count1),msort(Count1,Ans),write(Ans). test(Count,Deep,CardCH,CardCC):- !, move(0,0,CardCH, [0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2], 0,0,Count,Count1), Deep1 is Deep+1, card_shuffle(CardCH,CardCH1), card_shuffle(CardCC,CardCC1), test(Count1,Deep1,CardCH1,CardCC1). main84:-findall(C,counts(C),Counts), CardCH=[0,0,1,2,3,4,5,6,7,8,9,9,9,9,9,9], CardCC=[0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2], !, test(Counts,0,CardCH,CardCC). *Problem 81 「経路の和:2方向」 † http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2081 80要素を1行とする80行リストで実装したほうがよかったかも知れない問題。 コードが膨らんでしまった。 コードの半分が木構造の操作に使われたような気がする。 破壊的代入がないためにそれをごまかすひと手間がいたるところで発生して、コードが膨らんでいるという部分もある。 nth0を2回適用したほうがコードも短くシンプルで速度も大差ないのですが今回は木構造の勉強がしたかったということで一つ。 技術の勉強にと木構造に展開してみたけれど速くなったという実感がわかない。 破壊的代入がないから一々値を更新するたびに木の再構築を行っている。 これが遅いのかもしれないし単純に優先順位付きキューが使えない部分で遅くなっているのかもしれない。 高級言語すぎるとコンパイラやインタプリターが何をやっているかわかりづらくなるのが問題点かも。 そういうのを気にしたくないから高級化するのだが、高級化しすぎると何をしているのかわからなくなる。 % 破壊的代入がないからコードが恐ろしくめんどくさいことになっている % sakusya horie shinniti to_num([],Num,Num). to_num([X|Rest],Num,Result):-Num1 is Num*10+(X-48),to_num(Rest,Num1,Result). read81(List):- seen, see('e81.txt'), findall(X,read81oneRow(X),List). read81oneRow(Num):- repeat, peek_code(C), (C== -1 ->!,fail;true), findall(X,read81one(X),List), to_num(List,0,Num). read81one(A):- repeat, get0(A), ((48=<A,A=<57) ->true;!,fail). create_tree(Down,Up,[]):- Sa is Up-Down, Sa<2, !. create_tree(Down,Up,[Ls,-1,Rs]):- M is (Down+Up)//2, create_tree(Down,M,Ls), create_tree(M,Up,Rs). % 原理主義的に考えればこの述語が失敗した場合と成功した場合で処理を分けるべきだが、、、 % それをするとコードが膨らむのでやらない tree_update(Down,Up,P,Score,[Ls,Score1,Rs],[Ls,Score1,Rs1]):- M is (Down+Up)//2, M<P, !, tree_update(M,Up,P,Score,Rs,Rs1). tree_update(Down,Up,P,Score,[Ls,Score1,Rs],[Ls1,Score1,Rs]):- M is (Down+Up)//2, P<M, !, tree_update(Down,M,P,Score,Ls,Ls1). tree_update(_,_,_,Score,[Ls,Score1,Rs],[Ls,Score2,Rs]):- !, ((Score1== -1 ;Score<Score1)-> Score2 is Score; Score2 is Score1). tree_search(Down,Up,P,[_,_,Rs],Score1):- M is (Down+Up)//2, M<P, !, tree_search(M,Up,P,Rs,Score1). tree_search(Down,Up,P,[Ls,_,_],Score1):- M is (Down+Up)//2, P<M, !, tree_search(Down,M,P,Ls,Score1). tree_search(_,_,_,[_,Score,_],Score):- !. get_min([],Min,Min):-!. get_min([[Score,Row,Col]|Rest],[S1,_,_],Result):- Score<S1, !, get_min(Rest,[Score,Row,Col],Result). get_min([_|Rest],Min,Result):- !, get_min(Rest,Min,Result). one_move(Tree,ScoreTree,List,[],_):- !, search(Tree,ScoreTree,List). one_move(Tree,ScoreTree,List,[[Dx,Dy]|Rest],[Score,Row,Col]):- Row1 is Row+Dy, Col1 is Col+Dx, Row1<80, Col1<80, P is Row1*80+Col1, tree_search(-1,6400,P,Tree,Score1), Score2 is Score1+Score, tree_search(-1,6400,P,ScoreTree,Score3), (Score3== -1;Score2<Score3), !, tree_update(-1,6400,P,Score2,ScoreTree,ScoreTree1), one_move(Tree,ScoreTree1,[[Score2,Row1,Col1]|List],Rest,[Score,Row,Col]). one_move(Tree,ScoreTree,List,[_|Rest],Min):- !, one_move(Tree,ScoreTree,List,Rest,Min). search(_,_,List):- [Top|_]=List, get_min(List,Top,Min), [_,Row,Col]=Min, Row==79, Col==79, !, write([ans,Min]). search(Tree,ScoreTree,List):- [Top|_]=List, get_min(List,Top,Min), select(Min,List,List1), one_move(Tree,ScoreTree,List1,[[0,0],[1,0],[0,1]],Min). first(_,_,[],Tree):-!, tree_search(-1,6400,0,Tree,Score), create_tree(-1,6400,ScoreTree), search(Tree,ScoreTree,[[Score,0,0]]). first(Row,80,List,Tree):- !, Row1 is Row+1, first(Row1,0,List,Tree). first(Row,Col,[Score|List],Tree):- !, Col1 is Col+1, P is Row*80+Col, tree_update(-1,6400,P,Score,Tree,Tree1), first(Row,Col1,List,Tree1). test:-create_tree(-1,6400,Tree),read81(List), first(0,0,List,Tree). *問い82 問い81と大差ないので特に書くことなし % %sakusyahorie shinniti to_num([],Num,Num). to_num([X|Rest],Num,Result):-Num1 is Num*10+(X-48),to_num(Rest,Num1,Result). read82(List):- seen, see('e81.txt'), findall(X,read82oneRow(X),List). read82oneRow(Num):- repeat, peek_code(C), (C== -1 ->!,fail;true), findall(X,read82one(X),List), to_num(List,0,Num). read82one(A):- repeat, get0(A), ((48=<A,A=<57) ->true;!,fail). create_tree(Down,Up,[]):- Sa is Up-Down, Sa<2, !. create_tree(Down,Up,[Ls,-1,Rs]):- M is (Down+Up)//2, create_tree(Down,M,Ls), create_tree(M,Up,Rs). % % tree_update(Down,Up,P,Score,[Ls,Score1,Rs],[Ls,Score1,Rs1]):- M is (Down+Up)//2, M<P, !, tree_update(M,Up,P,Score,Rs,Rs1). tree_update(Down,Up,P,Score,[Ls,Score1,Rs],[Ls1,Score1,Rs]):- M is (Down+Up)//2, P<M, !, tree_update(Down,M,P,Score,Ls,Ls1). tree_update(_,_,_,Score,[Ls,Score1,Rs],[Ls,Score2,Rs]):- !, ((Score1== -1 ;Score<Score1)-> Score2 is Score; Score2 is Score1). tree_search(Down,Up,P,[_,_,Rs],Score1):- M is (Down+Up)//2, M<P, !, tree_search(M,Up,P,Rs,Score1). tree_search(Down,Up,P,[Ls,_,_],Score1):- M is (Down+Up)//2, P<M, !, tree_search(Down,M,P,Ls,Score1). tree_search(_,_,_,[_,Score,_],Score):- !. get_min([],Min,Min):-!. get_min([[Score,Row,Col]|Rest],[S1,_,_],Result):- Score<S1, !, get_min(Rest,[Score,Row,Col],Result). get_min([_|Rest],Min,Result):- !, get_min(Rest,Min,Result). one_move(Tree,ScoreTree,List,[],_):- !, search(Tree,ScoreTree,List). one_move(Tree,ScoreTree,List,[[Dx,Dy]|Rest],[Score,Row,Col]):- Row1 is Row+Dy, Col1 is Col+Dx, -1<Row1, Row1<80, Col1<80, P is Row1*80+Col1, tree_search(-1,6400,P,Tree,Score1), Score2 is Score1+Score, tree_search(-1,6400,P,ScoreTree,Score3), (Score3== -1;Score2<Score3), !, tree_update(-1,6400,P,Score2,ScoreTree,ScoreTree1), one_move(Tree,ScoreTree1,[[Score2,Row1,Col1]|List],Rest,[Score,Row,Col]). one_move(Tree,ScoreTree,List,[_|Rest],Min):- !, one_move(Tree,ScoreTree,List,Rest,Min). search(_,_,List):- [Top|_]=List, get_min(List,Top,Min), [_,_,Col]=Min, Col==79, !, write([ans,Min]). search(Tree,ScoreTree,List):- [Top|_]=List, get_min(List,Top,Min), select(Min,List,List1), one_move(Tree,ScoreTree,List1,[[0,-1],[1,0],[0,1]],Min). tree_first_set(Tree,ScoreTree,80,List):- !, search(Tree,ScoreTree,List). tree_first_set(Tree,ScoreTree,Row,List):- Row1 is Row+1, P is Row*80, tree_search(-1,6400,P,Tree,Score), tree_update(-1,6400,P,Score,ScoreTree,ScoreTree1), tree_first_set(Tree,ScoreTree1,Row1,[[Score,Row,0]|List]). first(_,_,[],Tree):-!, create_tree(-1,6400,ScoreTree), tree_first_set(Tree,ScoreTree,0,[]). first(Row,80,List,Tree):- !, Row1 is Row+1, first(Row1,0,List,Tree). first(Row,Col,[Score|List],Tree):- !, Col1 is Col+1, P is Row*80+Col, tree_update(-1,6400,P,Score,Tree,Tree1), first(Row,Col1,List,Tree1). test:-create_tree(-1,6400,Tree),read82(List), first(0,0,List,Tree). *問い83 これも81と大差なし特に書くことなし % %sakusyahorie shinniti to_num([],Num,Num). to_num([X|Rest],Num,Result):-Num1 is Num*10+(X-48),to_num(Rest,Num1,Result). read81(List):- seen, see('e81.txt'), findall(X,read81oneRow(X),List). read81oneRow(Num):- repeat, peek_code(C), (C== -1 ->!,fail;true), findall(X,read81one(X),List), to_num(List,0,Num). read81one(A):- repeat, get0(A), ((48=<A,A=<57) ->true;!,fail). create_tree(Down,Up,[]):- Sa is Up-Down, Sa<2, !. create_tree(Down,Up,[Ls,-1,Rs]):- M is (Down+Up)//2, create_tree(Down,M,Ls), create_tree(M,Up,Rs). % % tree_update(Down,Up,P,Score,[Ls,Score1,Rs],[Ls,Score1,Rs1]):- M is (Down+Up)//2, M<P, !, tree_update(M,Up,P,Score,Rs,Rs1). tree_update(Down,Up,P,Score,[Ls,Score1,Rs],[Ls1,Score1,Rs]):- M is (Down+Up)//2, P<M, !, tree_update(Down,M,P,Score,Ls,Ls1). tree_update(_,_,_,Score,[Ls,Score1,Rs],[Ls,Score2,Rs]):- !, ((Score1== -1 ;Score<Score1)-> Score2 is Score; Score2 is Score1). tree_search(Down,Up,P,[_,_,Rs],Score1):- M is (Down+Up)//2, M<P, !, tree_search(M,Up,P,Rs,Score1). tree_search(Down,Up,P,[Ls,_,_],Score1):- M is (Down+Up)//2, P<M, !, tree_search(Down,M,P,Ls,Score1). tree_search(_,_,_,[_,Score,_],Score):- !. get_min([],Min,Min):-!. get_min([[Score,Row,Col]|Rest],[S1,_,_],Result):- Score<S1, !, get_min(Rest,[Score,Row,Col],Result). get_min([_|Rest],Min,Result):- !, get_min(Rest,Min,Result). one_move(Tree,ScoreTree,List,[],_):- !, search(Tree,ScoreTree,List). one_move(Tree,ScoreTree,List,[[Dx,Dy]|Rest],[Score,Row,Col]):- Row1 is Row+Dy, Col1 is Col+Dx, Row1<80, Col1<80, -1<Row1, -1<Col1, P is Row1*80+Col1, tree_search(-1,6400,P,Tree,Score1), Score2 is Score1+Score, tree_search(-1,6400,P,ScoreTree,Score3), (Score3== -1;Score2<Score3), !, tree_update(-1,6400,P,Score2,ScoreTree,ScoreTree1), one_move(Tree,ScoreTree1,[[Score2,Row1,Col1]|List],Rest,[Score,Row,Col]). one_move(Tree,ScoreTree,List,[_|Rest],Min):- !, one_move(Tree,ScoreTree,List,Rest,Min). search(_,_,List):- [Top|_]=List, get_min(List,Top,Min), [_,Row,Col]=Min, Row==79, Col==79, !, write([ans,Min]). search(Tree,ScoreTree,List):- [Top|_]=List, get_min(List,Top,Min), select(Min,List,List1), one_move(Tree,ScoreTree,List1,[[0,-1],[-1,0],[1,0],[0,1]],Min). first(_,_,[],Tree):-!, tree_search(-1,6400,0,Tree,Score), create_tree(-1,6400,ScoreTree), tree_update(-1,6400,0,Score,ScoreTree,ScoreTree1), search(Tree,ScoreTree1,[[Score,0,0]]). first(Row,80,List,Tree):- !, Row1 is Row+1, first(Row1,0,List,Tree). first(Row,Col,[Score|List],Tree):- !, Col1 is Col+1, P is Row*80+Col, tree_update(-1,6400,P,Score,Tree,Tree1), first(Row,Col1,List,Tree1). test:-create_tree(-1,6400,Tree),read81(List), first(0,0,List,Tree). *問い85 N=1,M=2000から計算を初めて200万近辺だけを探索させました。 手法的には尺取り虫法です。 calcN(N,M,Re):-Re is (N*(N+1)*M*(M+1))//4. calcD(N,M,Sa,Ans,Sa,Ans):-M<N,!. calcD(N,M,Sa,Ans,ReSa,ReAns):- calcN(N,M,T), T<2000000, !, N1 is N+1, calcD(N1,M,Sa,Ans,ReSa,ReAns). calcD(N,M,Sa,Ans,ReSa,ReAns):- !, M1 is M-1, calcN(N,M,T), Sa1 is T-2000000, (Sa1<Sa->Sa2 is Sa1,Ans2 is N*M ;Sa2 is Sa,Ans2 is Ans ), calcD(N,M1,Sa2,Ans2,ReSa,ReAns). calcU(N,M,Sa,Ans,Sa,Ans):-M<N,!. calcU(N,M,Sa,Ans,ReSa,ReAns):- calcN(N,M,T), T<2000000, !, N1 is N+1, Sa1 is 2000000-T, (Sa1<Sa -> Sa2 is Sa1, Ans2 is N*M ; Sa2 is Sa, Ans2 is Ans ), calcU(N1,M,Sa2,Ans2,ReSa,ReAns). calcU(N,M,Sa,Ans,ReSa,ReAns):- !, M1 is M-1, calcU(N,M1,Sa,Ans,ReSa,ReAns). main85:- calcD(1,2000,2000000,0,Sa1,Ans1), calcU(1,2000,2000000,0,Sa2,Ans2), write([Sa1,Ans1,Sa2,Ans2]).
