2

我试图在 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.
4

8 回答 8

5

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

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

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

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

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

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

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).
于 2014-03-17T11:09:53.343 回答
2

请尝试以下操作：

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

取自各种语言的 GCD 上的rosettacode.org 。

于 2014-03-17T09:27:45.803 回答
1

GCD 的 Prolog 代码

gcd(X,Y,G) :- X=Y, G=X.
gcd(X,Y,G) :- X<Y, Y1 is Y-X, gcd(X,Y1,G).
gcd(X,Y,G) :- X>Y ,gcd(Y,X,G).

?- gcd(24,16,G).
G = 8
于 2014-11-26T17:44:37.707 回答
1 
gc(X,Y,Z):- (
    X=0 -> (
        Z is Y
    );
    Y=0 -> (
        Z is X
    );
    X=Y -> (
        Z is X
    );
    X>Y -> (
        Y1 is X-Y,
        gc(Y1,Y,Z)
    );
    X<Y->(
        Y1 is Y-X,
        gc(X,Y1,Z)
    )
).
于 2021-02-25T04:39:59.603 回答
0 
gcd(A,B,X):- B=0,X=A.

gcd(A,B,X):- A>B, gcd(B, A, X).

gcd(A,B,X) :- A<B, T is B mod A, gcd(A, T, X).
于 2018-06-30T05:47:30.240 回答
0

该代码有效。

gcd(X,X,X)。

gcd(X,Y,D):-X<Y, Y1 为 YX, gcd(X,Y1,D)。

gcd(X,Y,D):-Y<X, gcd(Y,X,D)。

于 2021-09-24T08:06:58.497 回答
0

序言的答案是：-

gcd(X,0,X).
gcd(X,Y,R):-
Y>0,
X1 is X mod Y,
gcd(Y,X1,R).
于 2017-11-20T19:18:29.807 回答
0

使用欧几里得算法的两个数的 GCD 的简单易读的 Prolog 代码。

gcd(A,B,X):- A=0,X=B. % base case
gcd(A,B,X):- B=0,X=A. % base case
gcd(A,B,X):- A>B, gcd(B, A, X).
gcd(A,B,X):- A<B, T is B mod A, gcd(A, T, X).

查询如下：

gcd(147,210,GCD).

输出：

GCD = 21
于 2019-11-26T10:28:23.613 回答