「prolog勉強プロジェクトオイラー101～110」の編集履歴（バックアップ）一覧に戻る

prolog勉強プロジェクトオイラー101～110 - (2013/10/12 (土) 05:21:59) の編集履歴(バックアップ)

---

プロジェクトオイラーの問題をPrologで解く堀江伸一さんのページ。

問い101「最適多項式」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20101
ニュートン補間を題材にした練習問題。
計算法や原理は分かったものの、Prologでどう実装したらよいかわからなかったのでとりあえずわかりやすさ重視でコードを実装。

f(N,Re):-Re is 1-N+N^2-N^3+N^4-N^5+N^6-N^7+N^8-N^9+N^10.
f2(N,Re):-Re is N^3.

g(X,[X1],Result):-Result is X-X1,!.
g(X,[X1|Xs],Result):-
	!,
	g(X,Xs,Re),
	Result is Re*(X-X1).
newton_calc(_,_,[C],C):-!.
newton_calc(X,[_|Xs],[C|Cs],Result):-
	newton_calc(X,Xs,Cs,ReY),
	g(X,Xs,MultX),
	Result is ReY+C*MultX.


newton(_,[Y],[Y]):-!.
newton([X|Xs],[Y|Ys],[C|Cs]):-
	!,
	newton(Xs,Ys,Cs),
	newton_calc(X,Xs,Cs,ReY),
	g(X,Xs,MultX),
	C is (Y-ReY)/MultX.

y_ calc(_,[_],[C],C):-!.
y_calc(X,[_|Xs],[C|Cs],ResultY):-
	y_calc(X,Xs,Cs,Re1),
	g(X,Xs,MultX),
 	ResultY is Re1+MultX*C.




calc(_,10,_,Sum):-write(Sum),!.
calc(Ys,X,Xs,Sum):-
	X1 is X+1,
 	f(X1,Y),
	Ys1=[Y|Ys],
	Xs1=[X1|Xs],
	X2 is X1+1,
	newton(Xs1,Ys1,Cs),
 	y_calc(X2,Xs1,Cs,Add),
	Sum1 is Sum+Add,
	write(Sum1),nl,
	calc(Ys1,X1,Xs1,Sum1).

main101:-calc([],0,[],0).

問い102 Triangle containment

http://projecteuler.net/problem=102
テキストファイルが読みにくかったのでテキストの内容をエディタでPrologのリスト形式に加工してから解。
解き方は自由のはずなのでこれはルール違反ではないはず。
原点Oが三角形ABCの内部にあるとはOAとOBの内積、OBとOCの内積、OCとOAの内積が全部同じ符号であるということ。
辺上にある場合の処理が問題に書いてないが、その場合も三角形内部にあるものと判定して計算でも合格できました。

calc([],Ans):-!,write(Ans).
calc([X1,Y1,X2,Y2,X3,Y3|Rest],Ans):-
	I1 is X1*Y2-X2*Y1,
	I2 is X2*Y3-X3*Y2,
	I3 is X3*Y1-X1*Y3,
 	((0=<I1,0=<I2,0=<I3);(I1=<0,I2=<0,I3=<0)),
	!,
	Ans1 is Ans+1,
	calc(Rest,Ans1).
calc([_,_,_,_,_,_|Rest],Ans):-
	calc(Rest,Ans).

main102:-
	seen,
	see('e102.txt'),
	read(X),
	seen,
	calc(X,0).