Prologの技芸 3.1節の練習問題

(1)

:- op(40,xfx,lt).
0 lt s(X) :- natural_number(X).
s(X) lt s(Y) :- X < Y.

:- op(40,xfx,gt).
s(X) gt 0 :- natural_number(X).
s(X) gt s(Y) :- X gt Y.

:- op(40,xfx,gteq).
X gteq 0 :- natural_number(X).
s(X) gteq s(Y) :- X gteq Y.

(3)

sn(0) =< sm(0)
sn-1(0) =< sm-1(0)
…
s(0) =< sm-n+1(0)
ここまででn個の節点
0 =< sm-n(0)
ここまででn+1個の節点
natural_number(sm-n(0))
natural_number(sm-n-1(0))
…
natural_number(s(0))
natural_number(0)
ここまででn+1+(m-n+1)=m+2個の節点

(4)

even(0).
even(s(s(X))) :- even(X).
odd(s(0)).
odd(s(s(X))) :- odd(X).

(5)

% fib(N,F) :-
% FはN番目のフィボナッチ数である．
fib(0,0).
fib(s(0),s(0)).
fib(s(s(N)),F) :- fib(N,F1), fib(s(N),F2), plus(F1,F2,F).

(6)

% divide(X,Y,Z) :-
%  Zは整数Xを整数Yで割った除数である．
divide(X,Y,s(Z)) :-
 X gteq Y, plus(Y,X1,X), divide(X1,Y,Z).
divide(X,Y,0) :- X lt Y.

(7)

% gcd(X,Y,Gcd) :-
%  GcdはXとYの最大公約数である．
gcd(0,X,X).
gcd(X,0,X).
gcd(X,Y,Gcd) :- X gteq Y, Y gt 0, plus(Y,Z,X), gcd(Y,Z,Gcd).
gcd(X,Y,Gcd) :- X lt Y, X gt 0, plus(X,Z,Y), gcd(X,Z,Gcd).