Prolog 中的 Euclid（最大公分母）

Question

我们得到了一个伪代码，我们应该将其翻译成 Prolog：

这是我能够想出的解决方案：

% if y = 0: return x
test(X, 0, Output) :- Output is X.
% if x = 0: return y
test(0, Y, Output) :- Output is Y.
% if if x > y: return euclid_recursive(x - y, y)
test(X,Y,Output) :- 
    % if x > y: return euclid_recursive(x - y, y)
    (   X > Y ->  Temp is X - Y ,
        test(Temp, Y,Output);
    % return euclid_recursive(x, y - x) 
        Temp is Y - X,
        test(X, Temp, Output)
    ).

我已经用几个示例对其进行了测试，它似乎可以工作。不过，如果你们能再看一眼，我将不胜感激。

Answer 1

您只需要使用is/2 [swi-doc] 来计算一个数值表达式。所以这里可以使用unification:

test(X, 0, X).
test(0, X, X).
test(X, Y, Output) :- 
    ( X > Y
    -> Temp is X - Y,
       test(Temp, Y,Output)
    ; Temp is Y - X,
      test(X, Temp, Output)
    ).

另一个主要问题是 Prolog 将继续进行递归调用，即使其中一个元素为零。因此它将不断提出新的解决方案：

?- test(36, 63, R).
R = 9 ;
R = 9 ;
R = 9 ;
R = 9 ;
R = 9 ;
R = 9 ;
R = 9 ;
R = 9 ;
R = 9 ;
R = 9 ;
R = 9 ;
R = 9 ;
…

这可能看起来不是（主要）问题，但如果您将 test/3 用作另一个程序的一部分，它可能会陷入无限循环，其中 test/3 不断提出 [=16] =]，下一个谓词调用每次都拒绝这个。

test(X, 0, X).
test(0, X, X) :-
    <b>X > 0</b>.
test(X, Y, Output) :- 
    <b>X > 0</b>,
    <b>Y > 0</b>,
    ( X > Y
    -> Temp is X - Y,
       test(Temp, Y,Output)
    ; Temp is Y - X,
      test(X, Temp, Output)
    ).

这只会提出一种解决方案：

?- test(36, 63, R).
R = 9 ;
false.

Prolog 中的 Euclid（最大公分母）

Euclid in Prolog (greatest common denominator)

recursion

prolog

greatest-common-divisor