このディレクトリの索引
#  出典: プログラミングのお題スレpart3
#  お題:原点と格子点(a,b)を結ぶ線分上にある格子点をすべて求める。
#  例
#  a=54, b=66 のとき
#  0 0
#  9 11
#  18 22
#  27 33
#  36 44
#  45 55
#  54 66 

'原点と格子点(a,b)を結ぶ線分上にある格子点をすべて求める。'(_a,_b,_格子点ならび) :-
'原点から格子点へのX方向,Y方向の刻みを求める'(_a,_b,_X方向への刻み,_Y方向への刻み),
'原点と格子点(a,b)を結ぶ線分上にある格子点をすべて求める。'(0,0,_a,_b,_X方向への刻み,_Y方向への刻み,_格子点ならび).

'原点と格子点(a,b)を結ぶ線分上にある格子点をすべて求める。'(X,Y,X,Y,_,_,[(X,Y)]) :- !.
'原点と格子点(a,b)を結ぶ線分上にある格子点をすべて求める。'(X_1,Y_1,_a,_b,_X方向への刻み,_Y方向への刻み,_格子点ならび) :-
刻みごとに格子点をすべて求める(X_1,Y_1,_a,_b,_X方向への刻み,_Y方向への刻み,_格子点ならび).

刻みごとに格子点をすべて求める(X_1,Y_1,_a,_b,_X方向への刻み,_Y方向への刻み,[(X_1,Y_1)|R]) :-
X_2 is X_1 + _X方向への刻み,
Y_2 is Y_1 + _Y方向への刻み,
'原点と格子点(a,b)を結ぶ線分上にある格子点をすべて求める。'(X_2,Y_2,_a,_b,_X方向への刻み,_Y方向への刻み,R).

'原点から格子点へのX方向,Y方向の刻みを求める'(_格子点のX座標,_格子点のY座標,_X方向への刻み,_Y方向への刻み) :-
格子点の絶対値の最大公約数(_格子点のX座標,_格子点のY座標,_格子点の_X_Y座標の絶対値の最大公約数),
'X方向とY方向の刻みを得る'(_格子点のX座標,_格子点のY座標,_格子点の_X_Y座標の絶対値の最大公約数,_X方向への刻み,_Y方向への刻み).

格子点の絶対値の最大公約数(_格子点のX座標,_格子点のY座標,_格子点の_X_Y座標の絶対値の最大公約数) :-
格子点の絶対値の(_格子点のX座標,_格子点のY座標,_格子点のX座標の絶対値,_格子点のY座標の絶対値),
最大公約数(_格子点のX座標の絶対値,_格子点のY座標の絶対値,_格子点の_X_Y座標の絶対値の最大公約数).

格子点の絶対値の(_格子点のX座標,_格子点のY座標,_格子点のX座標の絶対値,_格子点のY座標の絶対値) :-
_格子点のX座標の絶対値 is abs(_格子点のX座標),
_格子点のY座標の絶対値 is abs(_格子点のY座標).

'X方向とY方向の刻みを得る'(_格子点のX座標,_格子点のY座標,_格子点の_X_Y座標の絶対値の最大公約数,_X方向への刻み,_Y方向への刻み) :-
_X方向への刻み is _格子点のX座標 // _格子点の_X_Y座標の絶対値の最大公約数,
_Y方向への刻み is _格子点のY座標 // _格子点の_X_Y座標の絶対値の最大公約数.



最大公約数(M,N,_最大公約数) :-
最大公約数をユークリッドの互除法で求める(M,N,_最大公約数).

最大公約数をユークリッドの互除法で求める(M,N,N) :-
'MがNで割り切れたらNが最大公約数'(M,N),!.
最大公約数をユークリッドの互除法で求める(M,N,_最大公約数) :-
'MがNで割り切れなければ現在のNを余りで割っていく'(M,N,_最大公約数).

'MがNで割り切れたらNが最大公約数'(M,N) :-
0 is M mod N.

'MがNで割り切れなければ現在のNを余りで割っていく'(M,N,X) :-
'MがNで割り切れなければ'(M,N,_余り),
最大公約数をユークリッドの互除法で求める(N,_余り,X).

'MがNで割り切れなければ'(M,N,_余り) :-
_余り is M mod N,
0 =\= _余り.