在 Prolog 中查找 Gcd 的程序

Question

我试图在 Prolog 中编写代码来查找 GCD（不使用模）谁能告诉我这个程序有什么问题？

gcd(X,Y,Z):- X>=Y, X1=X-Y, gcd(X1,Y,Z).
gcd(X,Y,Z):- X<Y, X1=Y- X, gcd(X1,X,Z).
gcd(0,X,X):- X>0.

Answer 1

至于为什么原来的实现不起作用，有两个原因：

谓词=/2是为了统一，而不是算术赋值

表达X1 = X - Y不减去Y从X和结果存储在X1。相反，它X1与术语统一-(X,Y)。例如，如果X=5和Y=3，那么结果将是，X1=5-3，不是X1=2。解决方案是使用is/2which 分配计算的算术表达式：X1 is X - Y.

其他谓词，除了基本情况谓词，成功匹配基本情况

该子句gcd(0,X,X) :- X > 0.是一个合理的基本情况，但从未尝试过，因为第二个子句 ( gcd(X,Y,Z):- X<Y,...) 将始终首先成功匹配相同的条件，从而导致无限递归和堆栈溢出。

解决此问题的一种方法是将基本情况移至第一个子句，并在成功执行后使用 cut 避免回溯：

gcd(0, X, X):- X > 0, !.
gcd(X, Y, Z):- X >= Y, X1 is X-Y, gcd(X1,Y,Z).
gcd(X, Y, Z):- X < Y, X1 is Y-X, gcd(X1,X,Z).

现在这将起作用：

| ?- gcd(10,6,X).

X = 2 ? ;

(1 ms) no
| ?- gcd(10,5,X).

X = 5 ? ;

no

（注意：这里的“否”表示在找到第一个解决方案后没有找到更多解决方案）

附录

在上述实现中仍然存在一些剩余的“差距”。一是它不能gcd(0, 0, R)优雅地处理（它溢出）。其次，它不处理负值。一种可能的解决方案是详细说明这些情况：

gcd(X, Y, Z) :-
    X < 0, !,
    gcd(-X, Y, Z).
gcd(X, Y, Z) :-
    Y < 0, !,
    gcd(X, -Y, Z).
gcd(X, 0, X) :- X > 0.
gcd(0, Y, Y) :- Y > 0.
gcd(X, Y, Z) :-
    X > Y, Y > 0,
    X1 is X - Y,
    gcd(Y, X1, Z).
gcd(X, Y, Z) :-
    X =< Y, X > 0,
    Y1 is Y - X,
    gcd(X, Y1, Z).