「prolog勉強プロジェクトオイラー81～90」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
プロジェクトオイラーの問題を堀江伸一さんがProlog言語で解くページ
*Problem 86 「直方体のルート」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2086
この問題は普通に解くと2重ループで簡単に解けるので簡単すぎます、M＝1000万の場合の組み合わせ数を求める発展問題を考えてみました。
M=100で2060通りなら、M=1000万は何通りになるかということです。
M=1000万は考えるのが難しかったのでとりあえず最初C++でかきそれをPrologに翻訳しました、M=1000万はC++だと計算時間15秒で答えが出ます。
M=100万はPrologでも答えが出ますが、速度は遅いですね、M=1000万はPrologだとERROR: Out of global stackをはき無理でした。
このへんMをどうやって増大させるか後日の宿題にしたいところです。
C++のコード内容
1 基本的な考え方はファレイ数列の性質を利用して原始ピタゴラス数を最小辺が小さな順から取りだす。
それだけで後は組み合わせを計算しているだけです。
コンパイラはBCC C++で6秒で答えが出ます。
コード解説
自力で考えるのに3日かかりました。
直方体の縦横高さをA<=B<=Cと定義します
まず最初に考えたのは原始ピタゴラス数を求め縦横の長さを、a,bとしa<=bと考えます。
b<=2aならa=C,b=A+Bに分解した時の個数を計算します。
次にb=C a=A+Bと考えこれの組み合わせ数も計算します。
するとこの原始ピタゴラス数から求まる直方体の組み合わせが全て出ます。
この時定数倍も規則的に計算できるので一緒に計算します。
直感的に理解しているだけなのですが別の原始ピタゴラス数との重複はありません。
次に考えたのは原始ピタゴラス数を効率よく生成する方法でした。
ファレイ数列は原始ピタゴラス数の生成条件であるｎとｍが互いに素を満たしているのでファレイ数列を使うことを考えました。
ファレイ数列は、数列を生成すると
X=nl/ml Y=n/m Z=nr/mr
から
C=(nl+n)/(ml+m)
D=(nr+n)/(mr+m)
という数列を間に生み出します。
この時f(n,m)をm^2-n^2と2mnの小さい方を返す関数と考えると
f(C)>f(X) ∧ f(C)>f(Y)
f(D)>f(X) ∧ f(D)>f(Z)
となります。
これにより
G=(f(X),X,Y,Z)という要素をもつ構造体を考えf(X)の小さい順にスタックから取り出し、Gのｎ、ｍから生成できる組み合わせ数を求め答えとして足し算していきます。
Gの左右の分数を表すGLとGRを求めこの生成したGLとGRのf(X)が1000万以下ならスタックに戻します。
この操作を繰り返せば見事M＝1000万の時の組み合わせ数が一瞬でもとまるということになります。
スタック最大使用量1250000
Mが10000000の時の組み合わせ数61589103127262
と答えが出ています。
#include<stdio.h>
#include<stack>
#include <algorithm>
#include<iostream>
struct Fary{
__int64 nl,ml,n,m,nr,mr,minLen,longLen;
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::stack<Fary> quF;
Fary f,f1;
f.set_date(0,1,1,2,1,1);
quF.push(f);
__int64 ans=0;
__int64 size1=0;
__int64 max=1000*10000;
while(quF.empty()==false){
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が"<<max<<"の時の組み合わせ数"<<ans;
}
*問い86
問い86でM=100万の時の組み合わせ数を求めるProlog版コード。
C++のものをそのまま翻訳した。
calc_perm_sub(A,B,_,0):-A1 is 2*A,A1<B,!.
calc_perm_sub(A,B,Max,Result):-A<B,
!,
Sa is 2*A-B,
K is Max//A,
Result is (K*(K+1)*Sa)//4-(Sa mod 2)*((K+1)//4)+K.
calc_perm_sub(A,B,Max,Result):-
B<A,
!,
K is Max//A,
Result is (K*(K+1)*B)//4-(B mod 2)*((K+1)//4).
calc_perm_sub(_,_,_,0):-!.
calc_perm(N,M,Max,Result):-
!,
A is M*M-N*N,
B is 2*M*N,
((M-N) mod 2=:=0 ->Result is 0;
calc_perm_sub(A,B,Max,Re1),
calc_perm_sub(B,A,Max,Re2),
Result is Re1+Re2).
len_ok(N,M,Max):-L1 is M*M-N*N,L1=<Max,!.
len_ok(N,M,Max):-L1 is 2*M*N,L1=<Max,!.
create_L([NL,ML,N,M,_,_],[NL,ML,ReN,ReM,N,M],Max):-
ReN is NL+N,
ReM is ML+M,
len_ok(N,M,Max).
create_R([_,_,N,M,NR,MR],[N,M,ReN,ReM,NR,MR],Max):-
ReN is N+NR,
ReM is M+MR,
len_ok(N,M,Max).
add_R(Fary,List,Max,Ans):-
create_R(Fary,NextF,Max),
!,
search([NextF|List],Max,Ans).
add_R(_,List,Max,Ans):-
!,
search(List,Max,Ans).
add_L(Fary,List,Max,Ans):-
create_L(Fary,NextF,Max),
!,
add_R(Fary,[NextF|List],Max,Ans).
add_L(Fary,List,Max,Ans):-!,
add_R(Fary,List,Max,Ans).
search([],_,Ans):-write(Ans),!.
search([Fary|Rest],Max,Ans):-
!,
[_,_,N,M,_,_]=Fary,
calc_perm(N,M,Max,Perm),
Ans1 is Ans+Perm,
add_L(Fary,Rest,Max,Ans1).
main86:-search([[0,1,1,2,1,1]],1000000,0).
*問い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]).
*問い87
http://projecteuler.net/problem=87
単純な全探索以外何も思いつかないという意味では難問です。
他の方法で解けたらちょっとその人は賢いでしょうね。
何か賢い方法はあるのでしょうか？
深く考えると難問かもしれませんし、無理やり作った単なる探索の練習問題かもしれません。
この問題はその内賢い方法を思いついたら再挑戦するかもしれません。
out(N):-50000000=<N.
is_prime(N):-
N>1,
between(2,N,N1),
(N<N1*N1 -> true,!;0=:=N mod N1,!,fail).
p4(N4):-
between(2,84,N),
is_prime(N),
N4 is N^4.
p3(N3):-
between(2,368,N),
is_prime(N),
N3 is N^3.
p2(N2):-
between(2,7071,N),
is_prime(N),
N2 is N^2.
perm_sub([P|_],Sum,Rest,Result):-
Sum1 is Sum+P,
(out(Sum1)->!,fail;
perm(Rest,Sum1,Result)).
perm_sub([_|Ps],Sum,Rest,Result):-
perm_sub(Ps,Sum,Rest,Result).
perm([],Sum,Sum):-
not(out(Sum)).
perm([Ps|Rest],Sum,Result):-
perm_sub(Ps,Sum,Rest,Result).
main87:-findall(N4,p4(N4),Ps4),
findall(N3,p3(N3),Ps3),
findall(N2,p2(N2),Ps2),
!,
findall(N,perm([Ps4,Ps3,Ps2],0,N),Ans1),
sort(Ans1,Ans2),
length(Ans1,Len1),
length(Ans2,Len2),
write([Len1,Len2]).
*問い88
この問題は独力で解を思いつくのに苦労した。
Prologで効率的に実装する方法を思いつかなかったので、今回もBCC5.5 C++に逃げている。
小さい数から全探索で掛け算する数と足し算する数を計算し、その２つの差と足した数の個数の合計が12000以下ならそれは最小積和数の可能性があるのでstd::mapに登録する。
ｋが登録済みならより小さい方を残し、未登録のｋならそれをとりあえず暫定解として登録する。
というだけの簡単な処理で結構速度が出た。
後日Prologで実装する方法を考えたいがリスト処理では速度が出ない。
難しいところです。
#include<stdio.h>
#include<iostream>
#include<map>
#include<set>
std::map<int,int> memo;
std::map<int,int>::iterator it;
std::set<int> sets;
std::set<int>::iterator itS;
const __int64 up=12000;
void saiki(__int64 mult,__int64 sum,__int64 num,int deep){
__int64 k=mult-sum+deep;
if(k<=up&&deep>1){
int k1=k;
if(memo.find(k1)==memo.end()||mult<memo[k1])memo[k1]=mult;
}
__int64 mult1,sum1,a;
while(true){
mult1=mult*num;
sum1=sum+num;
if(deep==0&&mult1*mult1-sum1-sum1>up){
return ;
}
if(mult1-sum1<=up){
saiki(mult1,sum1,num,deep+1);
}else{
return ;
}
num++;
}
}
int main(){
saiki(1,0,2,0);
__int64 ans=0;
for(it=memo.begin();it!=memo.end();it++){
sets.insert((*it).second);
}
for(itS=sets.begin();itS!=sets.end();itS++){
ans+=(*itS);
}
std::cout<<ans;
}
*問い89
ローマ数字を最短で書いた場合何文字節約できるかという問題。
いかにもPrologみたいな感じでコードを書いてみた。
段階を追ってデータを処理しているため処理的に無駄が多いがわかりやすさ重視で記述。
扱うデータ量もたったの1000件だし無駄なんて気にしない。
rowlast('\n').
rowlast(end_of_file).
val('I',1):-!.
val('V',5):-!.
val('X',10):-!.
val('L',50):-!.
val('C',100):-!.
val('D',500):-!.
val('M',1000):-!.
min(X,2):-member(X,[2,4,6,9]),!.
min(X,1):-member(X,[1,5]),!.
min(X,3):-member(X,[3,7]),!.
min(8,4):-!.
min(0,0):-!.
one_read(X):-
repeat,
get_char(X),
(rowlast(X)->!,fail;true).
myread(List):-
repeat,
peek_code(A),
(A=:= -1->!,fail;findall(X,one_read(X),List)).
to_num([],Sum,Sum):-!.
to_num([X0,X1|Rest],Sum,Result):-
val(X0,V0),
val(X1,V1),
V0<V1,
!,
Sum1 is Sum+V1-V0,
to_num(Rest,Sum1,Result).
to_num([X|Rest],Sum,Result):-
!,
val(X,V),
Sum1 is Sum+V,
to_num(Rest,Sum1,Result).
lens_count([],Sum,Sum):-!.
lens_count([X|Rest],Sum,Result):-
!,
length(X,Len),
Sum1 is Sum+Len,
lens_count(Rest,Sum1,Result).
to_nums(List,Result):-
member(X,List),
to_num(X,0,Result).
min_len(0,Sum,Sum):-!.
min_len(X,Sum,Result):-
M is X mod 10,
min(M,Add),
Sum1 is Sum+Add,
X1 is X//10,
min_len(X1,Sum1,Result).
min_len_first(X,Result):-
!,
X1 is X mod 1000,
Sum is X //1000,
min_len(X1,Sum,Result).
min_lens(Nums,Result):-
member(N,Nums),
min_len_first(N,Result).
sum([],Sum,Sum):-!.
sum([X|Rest],Sum,Result):-
Sum1 is Sum+X,
sum(Rest,Sum1,Result).
main89:-seen,see('e89.txt'),findall(X,myread(X),List),
lens_count(List,0,Len1),
findall(X,to_nums(List,X),Nums),
findall(X,min_lens(Nums,X),AnsLen),
sum(AnsLen,0,Ans1),
write([Len1,Ans1]),
Ans2 is Len1-Ans1,
write(Ans2).
*問い90
この問題問題自体は簡単だけど仕様がわかりにくく書いていて解釈が難しい。
配列は無視すること。
ダイスに書いてある数字を小さい順に並べたものだけで区別される。
[1,2,3,4,5,6]と[1,2,3,4,5,9]
はこれを入れ替えた
[1,2,3,4,5,9]と[1,2,3,4,5,6]は別物として考える。
あるキューブの配列が[1,2,3,4,5,6,9]で6と9がある場合と6しかない場合9しかない場合は別の組み合わせとして計算する。
ということのようでこの考えで解けました。
n_add(N,List,[6,9|List]):-member(N,[6,9]),!.
n_add(N,List,[N|List]):-!.
perm(_,List,0,List1):-!,sort(List,List1).
perm(N,List,D,Result):-
Sa is 10-N,
(Sa=<D->!;true),
D1 is D-1,
N1 is N+1,
n_add(N,List,List1),
perm(N1,List1,D1,Result).
perm(N,List,D,Result):-!,
N1 is N+1,
perm(N1,List,D,Result).
set2([X|_],[X]).
set2([_|Rest],Result):-
set2(Rest,Result).
set1([X|Rest],[X|Result]):-
set2(Rest,Result).
set1([_|Rest],Result):-
set1(Rest,Result).
check(Xai1,Xai2,X1,X2):-
member(X1,Xai1),
member(X2,Xai2),
!.
check(Xai1,Xai2,X1,X2):-
member(X2,Xai1),
member(X1,Xai2),
!.
is_ok(_,_,[]):-!.
is_ok(Xai1,Xai2,[[X1,X2]|Rest]):-
!,
check(Xai1,Xai2,X1,X2),
is_ok(Xai1,Xai2,Rest).
search(List,1):-
set1(List,[Xai1,Xai2]),
is_ok(Xai1,Xai2,[[0,1],[0,4],[0,9],[1,6],[2,5],[3,6],[4,9],[6,4],[8,1]]).
main90:-findall(P,perm(0,[],6,P),List),
findall(X,search(List,X),Ans),
length(Ans,AnsLen),
write(AnsLen).
プロジェクトオイラーの問題を堀江伸一さんがProlog言語で解くページ
*Problem 86 「直方体のルート」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2086
この問題は普通に解くと2重ループで簡単に解けるので簡単すぎます、M＝1000万の場合の組み合わせ数を求める発展問題を考えてみました。
M=100で2060通りなら、M=1000万は何通りになるかということです。
M=1000万は考えるのが難しかったのでとりあえず最初C++でかきそれをPrologに翻訳しました、M=1000万はC++だと計算時間15秒で答えが出ます。
M=100万はPrologでも答えが出ますが、速度は遅いですね、M=1000万はPrologだとERROR: Out of global stackをはき無理でした。
このへんMをどうやって増大させるか後日の宿題にしたいところです。
C++のコード内容
1 基本的な考え方はファレイ数列の性質を利用して原始ピタゴラス数を最小辺が小さな順から取りだす。
それだけで後は組み合わせを計算しているだけです。
コンパイラはBCC C++で6秒で答えが出ます。
コード解説
自力で考えるのに3日かかりました。
直方体の縦横高さをA<=B<=Cと定義します
まず最初に考えたのは原始ピタゴラス数を求め縦横の長さを、a,bとしa<=bと考えます。
b<=2aならa=C,b=A+Bに分解した時の個数を計算します。
次にb=C a=A+Bと考えこれの組み合わせ数も計算します。
するとこの原始ピタゴラス数から求まる直方体の組み合わせが全て出ます。
この時定数倍も規則的に計算できるので一緒に計算します。
直感的に理解しているだけなのですが別の原始ピタゴラス数との重複はありません。
次に考えたのは原始ピタゴラス数を効率よく生成する方法でした。
ファレイ数列は原始ピタゴラス数の生成条件であるｎとｍが互いに素を満たしているのでファレイ数列を使うことを考えました。
ファレイ数列は、数列を生成すると
X=nl/ml Y=n/m Z=nr/mr
から
C=(nl+n)/(ml+m)
D=(nr+n)/(mr+m)
という数列を間に生み出します。
この時f(n,m)をm^2-n^2と2mnの小さい方を返す関数と考えると
f(C)>f(X) ∧ f(C)>f(Y)
f(D)>f(X) ∧ f(D)>f(Z)
となります。
これにより
G=(f(X),X,Y,Z)という要素をもつ構造体を考えf(X)の小さい順にスタックから取り出し、Gのｎ、ｍから生成できる組み合わせ数を求め答えとして足し算していきます。
Gの左右の分数を表すGLとGRを求めこの生成したGLとGRのf(X)が1000万以下ならスタックに戻します。
この操作を繰り返せば見事M＝1000万の時の組み合わせ数が一瞬でもとまるということになります。
スタック最大使用量1250000
Mが10000000の時の組み合わせ数61589103127262
と答えが出ています。
#include<stdio.h>
#include<stack>
#include <algorithm>
#include<iostream>
struct Fary{
__int64 nl,ml,n,m,nr,mr,minLen,longLen;
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::stack<Fary> quF;
Fary f,f1;
f.set_date(0,1,1,2,1,1);
quF.push(f);
__int64 ans=0;
__int64 size1=0;
__int64 max=1000*10000;
while(quF.empty()==false){
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が"<<max<<"の時の組み合わせ数"<<ans;
}
*問い86
問い86でM=100万の時の組み合わせ数を求めるProlog版コード。
C++のものをそのまま翻訳した。
calc_perm_sub(A,B,_,0):-A1 is 2*A,A1<B,!.
calc_perm_sub(A,B,Max,Result):-A<B,
!,
Sa is 2*A-B,
K is Max//A,
Result is (K*(K+1)*Sa)//4-(Sa mod 2)*((K+1)//4)+K.
calc_perm_sub(A,B,Max,Result):-
B<A,
!,
K is Max//A,
Result is (K*(K+1)*B)//4-(B mod 2)*((K+1)//4).
calc_perm_sub(_,_,_,0):-!.
calc_perm(N,M,Max,Result):-
!,
A is M*M-N*N,
B is 2*M*N,
((M-N) mod 2=:=0 ->Result is 0;
calc_perm_sub(A,B,Max,Re1),
calc_perm_sub(B,A,Max,Re2),
Result is Re1+Re2).
len_ok(N,M,Max):-L1 is M*M-N*N,L1=<Max,!.
len_ok(N,M,Max):-L1 is 2*M*N,L1=<Max,!.
create_L([NL,ML,N,M,_,_],[NL,ML,ReN,ReM,N,M],Max):-
ReN is NL+N,
ReM is ML+M,
len_ok(N,M,Max).
create_R([_,_,N,M,NR,MR],[N,M,ReN,ReM,NR,MR],Max):-
ReN is N+NR,
ReM is M+MR,
len_ok(N,M,Max).
add_R(Fary,List,Max,Ans):-
create_R(Fary,NextF,Max),
!,
search([NextF|List],Max,Ans).
add_R(_,List,Max,Ans):-
!,
search(List,Max,Ans).
add_L(Fary,List,Max,Ans):-
create_L(Fary,NextF,Max),
!,
add_R(Fary,[NextF|List],Max,Ans).
add_L(Fary,List,Max,Ans):-!,
add_R(Fary,List,Max,Ans).
search([],_,Ans):-write(Ans),!.
search([Fary|Rest],Max,Ans):-
!,
[_,_,N,M,_,_]=Fary,
calc_perm(N,M,Max,Perm),
Ans1 is Ans+Perm,
add_L(Fary,Rest,Max,Ans1).
main86:-search([[0,1,1,2,1,1]],1000000,0).
*問い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]).
*問い87
http://projecteuler.net/problem=87
単純な全探索以外何も思いつかないという意味では難問です。
他の方法で解けたらちょっとその人は賢いでしょうね。
何か賢い方法はあるのでしょうか？
深く考えると難問かもしれませんし、無理やり作った単なる探索の練習問題かもしれません。
この問題はその内賢い方法を思いついたら再挑戦するかもしれません。
out(N):-50000000=<N.
is_prime(N):-
N>1,
between(2,N,N1),
(N<N1*N1 -> true,!;0=:=N mod N1,!,fail).
p4(N4):-
between(2,84,N),
is_prime(N),
N4 is N^4.
p3(N3):-
between(2,368,N),
is_prime(N),
N3 is N^3.
p2(N2):-
between(2,7071,N),
is_prime(N),
N2 is N^2.
perm_sub([P|_],Sum,Rest,Result):-
Sum1 is Sum+P,
(out(Sum1)->!,fail;
perm(Rest,Sum1,Result)).
perm_sub([_|Ps],Sum,Rest,Result):-
perm_sub(Ps,Sum,Rest,Result).
perm([],Sum,Sum):-
not(out(Sum)).
perm([Ps|Rest],Sum,Result):-
perm_sub(Ps,Sum,Rest,Result).
main87:-findall(N4,p4(N4),Ps4),
findall(N3,p3(N3),Ps3),
findall(N2,p2(N2),Ps2),
!,
findall(N,perm([Ps4,Ps3,Ps2],0,N),Ans1),
sort(Ans1,Ans2),
length(Ans1,Len1),
length(Ans2,Len2),
write([Len1,Len2]).
*問い88
この問題は独力で解を思いつくのに苦労した。
Prologで効率的に実装する方法を思いつかなかったので、今回もBCC5.5 C++に逃げている。
小さい数から全探索で掛け算する数と足し算する数を計算し、その２つの差と足した数の個数の合計が12000以下ならそれは最小積和数の可能性があるのでstd::mapに登録する。
ｋが登録済みならより小さい方を残し、未登録のｋならそれをとりあえず暫定解として登録する。
というだけの簡単な処理で結構速度が出た。
後日Prologで実装する方法を考えたいがリスト処理では速度が出ない。
難しいところです。
#include<stdio.h>
#include<iostream>
#include<map>
#include<set>
std::map<int,int> memo;
std::map<int,int>::iterator it;
std::set<int> sets;
std::set<int>::iterator itS;
const __int64 up=12000;
void saiki(__int64 mult,__int64 sum,__int64 num,int deep){
__int64 k=mult-sum+deep;
if(k<=up&&deep>1){
int k1=k;
if(memo.find(k1)==memo.end()||mult<memo[k1])memo[k1]=mult;
}
__int64 mult1,sum1,a;
while(true){
mult1=mult*num;
sum1=sum+num;
if(deep==0&&mult1*mult1-sum1-sum1>up){
return ;
}
if(mult1-sum1<=up){
saiki(mult1,sum1,num,deep+1);
}else{
return ;
}
num++;
}
}
int main(){
saiki(1,0,2,0);
__int64 ans=0;
for(it=memo.begin();it!=memo.end();it++){
sets.insert((*it).second);
}
for(itS=sets.begin();itS!=sets.end();itS++){
ans+=(*itS);
}
std::cout<<ans;
}
*問い89
ローマ数字を最短で書いた場合何文字節約できるかという問題。
いかにもPrologみたいな感じでコードを書いてみた。
段階を追ってデータを処理しているため処理的に無駄が多いがわかりやすさ重視で記述。
扱うデータ量もたったの1000件だし無駄なんて気にしない。
rowlast('\n').
rowlast(end_of_file).
val('I',1):-!.
val('V',5):-!.
val('X',10):-!.
val('L',50):-!.
val('C',100):-!.
val('D',500):-!.
val('M',1000):-!.
min(X,2):-member(X,[2,4,6,9]),!.
min(X,1):-member(X,[1,5]),!.
min(X,3):-member(X,[3,7]),!.
min(8,4):-!.
min(0,0):-!.
one_read(X):-
repeat,
get_char(X),
(rowlast(X)->!,fail;true).
myread(List):-
repeat,
peek_code(A),
(A=:= -1->!,fail;findall(X,one_read(X),List)).
to_num([],Sum,Sum):-!.
to_num([X0,X1|Rest],Sum,Result):-
val(X0,V0),
val(X1,V1),
V0<V1,
!,
Sum1 is Sum+V1-V0,
to_num(Rest,Sum1,Result).
to_num([X|Rest],Sum,Result):-
!,
val(X,V),
Sum1 is Sum+V,
to_num(Rest,Sum1,Result).
lens_count([],Sum,Sum):-!.
lens_count([X|Rest],Sum,Result):-
!,
length(X,Len),
Sum1 is Sum+Len,
lens_count(Rest,Sum1,Result).
to_nums(List,Result):-
member(X,List),
to_num(X,0,Result).
min_len(0,Sum,Sum):-!.
min_len(X,Sum,Result):-
M is X mod 10,
min(M,Add),
Sum1 is Sum+Add,
X1 is X//10,
min_len(X1,Sum1,Result).
min_len_first(X,Result):-
!,
X1 is X mod 1000,
Sum is X //1000,
min_len(X1,Sum,Result).
min_lens(Nums,Result):-
member(N,Nums),
min_len_first(N,Result).
sum([],Sum,Sum):-!.
sum([X|Rest],Sum,Result):-
Sum1 is Sum+X,
sum(Rest,Sum1,Result).
main89:-seen,see('e89.txt'),findall(X,myread(X),List),
lens_count(List,0,Len1),
findall(X,to_nums(List,X),Nums),
findall(X,min_lens(Nums,X),AnsLen),
sum(AnsLen,0,Ans1),
write([Len1,Ans1]),
Ans2 is Len1-Ans1,
write(Ans2).
*問い90
この問題問題自体は簡単だけど仕様がわかりにくく書いていて解釈が難しい。
配列は無視すること。
ダイスに書いてある数字を小さい順に並べたものだけで組み合わせは区別される。
[1,2,3,4,5,6]と[1,2,3,4,5,9]
はこれを入れ替えた
[1,2,3,4,5,9]と[1,2,3,4,5,6]は同じものとみなす。
あるキューブの配列が[1,2,3,4,5,6,9]で6と9がある場合と6しかない場合9しかない場合は別の組み合わせとして計算する。
ということのようでこの考えで解けました。
n_add(N,List,[6,9|List]):-member(N,[6,9]),!.
n_add(N,List,[N|List]):-!.
perm(_,List,0,List1):-!,sort(List,List1).
perm(N,List,D,Result):-
Sa is 10-N,
(Sa=<D->!;true),
D1 is D-1,
N1 is N+1,
n_add(N,List,List1),
perm(N1,List1,D1,Result).
perm(N,List,D,Result):-!,
N1 is N+1,
perm(N1,List,D,Result).
set2([X|_],[X]).
set2([_|Rest],Result):-
set2(Rest,Result).
set1([X|Rest],[X|Result]):-
set2(Rest,Result).
set1([_|Rest],Result):-
set1(Rest,Result).
check(Xai1,Xai2,X1,X2):-
member(X1,Xai1),
member(X2,Xai2),
!.
check(Xai1,Xai2,X1,X2):-
member(X2,Xai1),
member(X1,Xai2),
!.
is_ok(_,_,[]):-!.
is_ok(Xai1,Xai2,[[X1,X2]|Rest]):-
!,
check(Xai1,Xai2,X1,X2),
is_ok(Xai1,Xai2,Rest).
search(List,1):-
set1(List,[Xai1,Xai2]),
is_ok(Xai1,Xai2,[[0,1],[0,4],[0,9],[1,6],[2,5],[3,6],[4,9],[6,4],[8,1]]).
main90:-findall(P,perm(0,[],6,P),List),
findall(X,search(List,X),Ans),
length(Ans,AnsLen),
write(AnsLen).
