「prolog勉強プロジェクトオイラー81~90」の編集履歴(バックアップ)一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
プロジェクトオイラーの問題を堀江伸一さんがProlog言語で解くページ
*Problem 86 「直方体のルート」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2086
この問題は普通に解くと2重ループで簡単に解けるので簡単すぎます、M=100万までの場合の組み合わせ数を求める発展問題を考えてみました。
流石にM=100万だとPrologではきついので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と考えこれの組み合わせ数も計算します。
するとこの原始ピタゴラス数から求まる直方体の組み合わせが全て出ます。
この時定数倍も規則的に計算できるので一緒に計算します。
直感的に理解しているだけなのですが別の原始ピタゴラス数との重複はありません。
次に考えたのは原始ピタゴラス数を効率よく生成する方法でした。
ファレイ数列は原始ピタゴラス数の生成条件であるnとmが互いに素を満たしているのでファレイ数列を使うことを考えました。
ファレイ数列は、数列を生成すると
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(Y) ∧ f(Z)
f(D)>以下同上
となります。
これにより
G=(f(X),X,Y,Z)という要素をもつ構造体を考えf(X)の小さい順に優先順位付きキューから取り出し、Gのn、mから生成できる組み合わせ数を求め
Gの左右の分数を計算してこの生成したf(X)が100万以下ならキューに戻します。
この操作を繰り返せば見事M=100万の時の組み合わせ数が一瞬でも止まるということになります。
優先順位付きキュー最大使用量1248192
Mの最大が1000000の時の組み合わせ数532281148674
と答えが出ています。
#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]).
*問い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++に逃げている。
小さい数から全探索で掛け算する数と足し算する数を計算し、その2つの差と足した数の個数の合計が12000以下ならそれは最小積和数の可能性があるのでstd::mapに登録する。
kが登録済みならより小さい方を残し、未登録のkならそれをとりあえず暫定解として登録する。
というだけの簡単な処理で結構速度が出た。
後日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;
}
プロジェクトオイラーの問題を堀江伸一さんがProlog言語で解くページ
*Problem 86 「直方体のルート」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2086
この問題は普通に解くと2重ループで簡単に解けるので簡単すぎます、M=100万までの場合の組み合わせ数を求める発展問題を考えてみました。
流石にM=100万だとPrologではきついので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と考えこれの組み合わせ数も計算します。
するとこの原始ピタゴラス数から求まる直方体の組み合わせが全て出ます。
この時定数倍も規則的に計算できるので一緒に計算します。
直感的に理解しているだけなのですが別の原始ピタゴラス数との重複はありません。
次に考えたのは原始ピタゴラス数を効率よく生成する方法でした。
ファレイ数列は原始ピタゴラス数の生成条件であるnとmが互いに素を満たしているのでファレイ数列を使うことを考えました。
ファレイ数列は、数列を生成すると
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(Y) ∧ f(Z)
f(D)>以下同上
となります。
これにより
G=(f(X),X,Y,Z)という要素をもつ構造体を考えf(X)の小さい順に優先順位付きキューから取り出し、Gのn、mから生成できる組み合わせ数を求め答えとして足し算していきます。
Gの左右の分数を表すGLとGRを求めこの生成したGLとGRのf(X)が100万以下ならキューに戻します。
この操作を繰り返せば見事M=100万の時の組み合わせ数が一瞬でも止まるということになります。
優先順位付きキュー最大使用量1248192
Mの最大が1000000の時の組み合わせ数532281148674
と答えが出ています。
#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]).
*問い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++に逃げている。
小さい数から全探索で掛け算する数と足し算する数を計算し、その2つの差と足した数の個数の合計が12000以下ならそれは最小積和数の可能性があるのでstd::mapに登録する。
kが登録済みならより小さい方を残し、未登録のkならそれをとりあえず暫定解として登録する。
というだけの簡単な処理で結構速度が出た。
後日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;
}