※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「prolog勉強プロジェクトオイラー91~100」の編集履歴(バックアップ)一覧に戻る

prolog勉強プロジェクトオイラー91~100 - (2013/09/11 (水) 19:15:41) のソース

プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。
*問い91
原点が特殊処理が必要なくらいで後は点OAのベクトルを90度回して最小公倍数でその長さ割ったベクトルの定数倍になる点を数えればOK。

 gcd(0, B, B).
 gcd(A, B, G) :- A > 0, R is B mod A, gcd(R, A, G). 
 
 min(X,Y,X):-X<Y,!.
 min(_,Y,Y):-!.
 
 point_count(_,0,1000):-!.
 point_count(L,D,Result):-
 	Result is L//D.
 
 r90(0,_,1,0):-!.
 r90(_,0,0,1):-!.
 r90(DY,DX,DY1,DX1):-
 	gcd(DY,DX,G),
 	DY1 is DX//G,
 	DX1 is DY//G.
  
 calc_perm(Y,X,Ans,Ans1):-
 	r90(Y,X,DY,DX),
 	X1 is 50-X,
 	Y1 is 50-Y,
	point_count(X ,DX,T1),
 	point_count(Y1,DY,T2),
  	point_count(X1,DX,T3),
 	point_count(Y,DY,T4),
 	min(T1,T2,Re1),
 	min(T3,T4,Re2),
 	Ans1 is Ans+Re1+Re2.
 
 search(51,0,Ans):-!,write(Ans).
 search(Y,51,Ans):-
 	!,
 	Y1 is Y+1,
 	search(Y1,0,Ans).
 search(Y,X,Ans):-
 	calc_perm(Y,X,Ans,Ans1),
 	X1 is X+1,
 	search(Y,X1,Ans1).
 
 main91:-search(0,1,2500).




*問い92
この問題はC++なら配列を使えば結構な速度で答えが出る。
Prologでは遅い。
少しだけ工夫が必要だ問題の関数をfと定義すると。
f(102345)=f(201345)
のように数字を並べ替えたものは同じ値になることとどうやら
f(1~9999999)<=567
となることを利用して計算量を下げれそうに見える。
これで試してみることにする。
只今コード準備中。