prolog - 序言中的二分法

Question

我写了以下代码：

nat(0).
nat(s(X)) :- nat(X).
divide(0,_,0).
divide(X,Y,D) :- X@<Y, D is 0.
divide(X,s(0),X).
divide(_,0,undefined) :- !.

一切都到这里为止。但是我应该写什么来计算另外两个自然数的除法？例如

divide(s(s(s(s(s(s(s(s(0)))))))),s(s(0)),D).???

Answer 1

我认为最简单的方法是定义减法，然后用计数器递归地应用它。我现在无法运行它，但我认为它看起来像这样：

nat(0).
nat(s(X)) :- nat(X).

divide(_,0,_):- !, fail.
divide(X,Y,R):-
    iter_subtract(X,Y,0,R).

iter_subtract(X,Y,N,N):- X@<Y, !.
iter_subtract(X,Y,C,R):-
    subtract(X,Y,N),
    D = s(C),
    iter_subtract(N,Y,D,R).

subtract(A,0,A):-!.
subtract(s(X),s(B),R):-
    subtract(X,B,R).

Answer 2

您可以轻松地划分两个数字，如下所示：

mydiv(0,_,0).
mydiv(_,0,undefined):- !.
mydiv(X,Y,D) :- X >= Y , Z is X - Y , mydiv(Z,Y,M) , D is M + 1  .

输出：

?- mydiv(10,4,Q)。
错误的。

?- mydiv(100,2,Q)。
Q = 50。

使用调试信息运行：

mydiv(0,_,0) :- write('mydiv(0,_,0)\n').
mydiv(_,0,undefined):- write('mydiv(_,0,undefined)\n'),!.
mydiv(X,Y,D) :- write('mydiv('),write(X) , write(','), write(Y) , write(',') , write(D) , write(')') , nl,
                X >= Y , Z is X - Y , mydiv(Z,Y,M) , D is M + 1  .

输出：

?- mydiv(20,2,Q)。
mydiv(20,2,_G3941) mydiv(18,2,_L1420
)
mydiv(16,2,_L1435)
mydiv(14,2,_L1450)
mydiv(12,2,_L1465)
mydiv(10,2,_L1480)
mydiv( 8,2,_L1495)
mydiv(6,2,_L1510)
mydiv(4,2,_L1525)
mydiv(2,2,_L1540)
mydiv(0,__,0)
Q = 10 。

具有自然功能：

natural(0).
natural(X) :- X < 0 , !, fail.
natural(X) :- Y is X - 1 , natural(Y).
mydiv(0,_,0) :- write('mydiv(0,_,0)\n').
mydiv(_,0,undefined):- write('mydiv(_,0,undefined)\n'),!.
mydiv(X,Y,D) :- write('mydiv('),write(X) , write(','), write(Y) , write(',') , write(D) , write(')') , nl,
                natural(X), natural(Y), X >= Y , Z is X - Y , mydiv(Z,Y,M) , D is M + 1  .