3

我有这段代码，它使用一个上限变量 N，它应该终止于勾股三元组的 X 和 Y。然而，它只有在达到上限时才会冻结。不知道如何使用剪切来停止回溯。代码是：

is_int(0).
is_int(X) :- is_int(Y), X is Y+1.
minus(S,S,0).
minus(S,D1,D2) :- S>0, S1 is S-1, minus(S1,D1,D3), D2 is D3+1.

pythag(X,Y,Z,N) :- int_triple(X,Y,Z,N), Z*Z =:= X*X + Y*Y.

int_triple(X,Y,Z,N) :- is_int(S), minus(S,X,S1), X>0, X<N,
                                  minus(S1,Y,Z), Y>0, Y<N.

将被称为，例如，

?- pythag(X,Y,Z,20).
4

2 回答 2

6

首先，让我们测试您的解决方案：

?- pythag(X,Y,Z,20)。
X = 4,
Y = 3，
Z = 5 ;
X = 3,
Y = 4,
Z = 5 ;
X = 8,
Y = 6，
Z = 10 ;
X = 6,
Y = 8,
Z = 10 ;
X = 12,
Y = 5,
Z = 13 ;
X = 5,
Y = 12,
Z = 13 ;
X = 12,
Y = 9,
Z = 15 ;
X = 9,
Y = 12,
Z = 15 ;
X = 15,
Y = 8,
Z = 17 ;
X = 8,
Y = 15,
Z = 17 ;
X = 16,
Y = 12,
Z = 20 ;
X = 12,
Y = 16，
Z = 20 ...

对我来说看起来很完美！所有答案都是正确的解决方案！...直到并包括最后一个解决方案。之后，您的程序循环。

在我们尝试找出问题之前，请稍等片刻：您必须非常耐心地通过 12 个（即：12 个）答案才找到那个循环。你认为这种方法也适用于更大的情况吗？在你放弃之前，你愿意看多少个答案？难道没有更简单的方法来找出问题吗？

这里有一个有趣的观察：找到的答案（几乎）与程序的循环无关！那就是：通过查看答案，您（通常 - 在这种情况下）对循环的实际原因一无所知！那么为什么不关闭所有答案并专注于相关部分！事实上，我们可以这样做：

?- pythag(X,Y,Z,20)，假的。
** 环形 **

现在，由于目标，所有答案都已被删除false。剩下的只是最终结果：要么终止，要么不终止，要么出现一些错误。没有其他的。这应该有助于我们对终止的观察——不再有令人眼花缭乱的答案在屏幕上滚动。请注意，这通常不能解决问题。毕竟，我们愿意等多久？1秒？1米？

未终止的实际原因可以通过查看相关故障切片来最好地理解。那是程序的一个片段，其不终止意味着整个程序的不终止。有关更多详细信息，请参阅此答案。这是您的查询程序的相关失败片段pythag(X,Y,Z,20), false：

毕达格（X，Y，Z，N）：-
   int_triple(X,Y,Z,N), false ,
    Z*Z =:= X*X + Y*Y。

int_triple(X,Y,Z,N) :-
   is_int(S), false ,
    minus(S,X,S1), X>0, X<N ,
    minus(S1,Y,Z), Y>0, Y<N。

is_int(0) :- 假。
is_int(X) :-
   is_int(Y)，假，
   X 为 Y+1。

请注意，您的程序所剩无几。例如，实际的方程式已经消失（这或多或少是逻辑部分......）。不过，这个片段是相关的。只要您不更改该片段中的某些内容，问题就会持续存在！对于一个纯粹的单调程序，这是保证的，因为这个......

这是我的首选解决方案：它使用length/2and between/3，两个经常支持的Prolog prologue谓词。

pythag2(X,Y,Z,N) :-
   长度（_，N），
   在（1，N，X）之间，
   在（1，N，Y）之间，
   在（1，N，Z）之间，
   Z*Z =:= X*X + Y*Y。
于 2012-05-09T13:22:16.780 回答
3

我最近也在考虑寻找毕达哥拉斯三元组的 Prolog 解决方案。我想出了一个稍微不同的代码。假设我们有一个函数：

isqrt(a) = floor(sqrt(a))

然后枚举 x 和 y 并检查 x*x+y*y 是否是某个 z 的平方就足够了。即检查：

h = x*x+y*y, z = isqrt(h), z*z = h ?

函数 iqrt 可以通过二分法实现。对于对称性破坏，我们可以在 x 之后枚举 y。假设 N = 99，结果代码为：

% between(+Integer, +Integer, -Integer)
between(Lo, Hi, _) :-
   Lo > Hi, !, fail.
between(Lo, _, Lo).
between(Lo, Hi, X) :-
   Lo2 is Lo+1, between(Lo2, Hi, X).

% bisect(+Integer, +Integer, +Integer, -Integer)
bisect(Lo, Hi, X, Y) :-
    Lo+1 < Hi, !,
    M is (Lo+Hi) // 2,
    S is M*M,
    (S > X -> bisect(Lo, M, X, Y);
     S < X -> bisect(M, Hi, X, Y);
     M = Y).
bisect(Lo, _, _, Lo).

% pythago(-List)
pythago(X) :-
   X = [A,B,C],
   between(1, 99, A),
   between(A, 99, B),
   H is A*A+B*B,
   bisect(0, H, H, C),
   C =< 99, H =:= C*C.

应该有 50 个这样的毕达哥拉斯三元组，另见Sloan 的 A046083：

?- findall(-, pythago(_), L), length(L, N).
N = 52.

人们可能想与以下 CLP(FD) 解决方案进行交叉检查。

:- use_module(library(clpfd)).

% pythago3(-List)
pythago3(X) :-
   X = [A,B,C],
   X ins 1..99,
   A*A+B*B #= C*C,
   A #=< B,
   label(X).

它提供了相同数量的解决方案：

?- findall(-, pythago3(_), L), length(L, N).
N = 50.
于 2013-08-31T21:06:01.080 回答