Prolog - 获取给定数字的因子不会停止吗？

Question

我需要找到给定数字的因数，例如:

?- divisors2(40,R).
R = [40,20,10,8,5,4,2,1].

代码:

% get all the numbers between 1-X 
range(I,I,[I]).
range(I,K,[I|L]) :- I < K, I1 is I + 1, range(I1,K,L).
% calc the modulo of each element with the given number :
% any x%y=0 would be considered as part of the answer 
divisors1([],[],_).
divisors1([H|T],S,X):-divisors1(T,W,X),Z is X mod H,Z==0,S=[H|W].
divisors1([_|T],S,X):-divisors1(T,S,X).
divisors2(X,Result) :-range(1,X,Result1),divisors1(Result1,Result,X).

但是当我运行 divisors2(40,RR). 时，我遇到了无限循环，并且屏幕上没有显示任何内容。

为什么？

问候

Answer 1

您问为什么查询divisors2(40,R)会出现无限循环。我几乎想用 failure-slice 向你解释这一点。唉...

...答案是:不，你不会得到无限循环!你的程序也会找到答案。这是

   R = [1,2,4,5,8,10,20,40]

这对我来说看起来很合理。它们按升序排列，而您想要一个降序列表，但除此之外，这是一个完美的答案。不开玩笑。不过，我怀疑你没有足够的耐心得到答案。对于 36，我需要:

?- time(divisors2(36,R)).
   % 10,744,901,605 inferences, 2248.800 CPU in 2252.918 seconds (100% CPU, 4778061 Lips)
   R = [1,2,3,4,6,9,12,18,36]
;  ... .

相当不寻常...对于最多包含 36 个微不足道整数的列表，Prolog 需要 10 744 901 605 次推理，这少于 2³⁴。这是否敲响了警钟？不管怎样，你的程序有问题。事实上，存在两个相当独立的问题。我们怎样才能找到他们？

也许我们看错了方向。回到查询就可以了。我们的第一个错误是我们如何使用 Prolog 的顶层。得到答案给我们留下了深刻的印象。但 Prolog 为我们提供了进一步的答案!事实上:

?- time(divisors2(36,R)).
   % 10,744,901,605 inferences, 2248.800 CPU in 2252.918 seconds (100% CPU, 4778061 Lips)
   R = [1,2,3,4,6,9,12,18,36]
;  % 10 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 455892 Lips)  R = [1,2,3,4,6,9,12,18]
;  % 917,508 inferences, 0.192 CPU in 0.192 seconds (100% CPU, 4789425 Lips)
   R = [1,2,3,4,6,9,12,36]
; ... .

这太乏味了。也许一个小例子就足够了？

?- divisors2(6,R).
   R = [1,2,3,6]
;  R = [1,2,3]
;  R = [1,2,6]
;  R = [1,2]
;  R = [1,3,6]
;  R = [1,3]
;  R = [1,6]
;  R = [1]
;  R = [2,3,6]
;  R = [2,3]
;  R = [2,6]
;  R = [2]
;  R = [3,6]
;  R = [3]
;  R = [6]
;  R = []
;  false.

绰绰有余!也许我们坚持使用最小的示例 [] 并重述它:

?- divisors2(6,[]).
   true
;  false.

显然，这不是我们所期望的。我们希望这件事失败。如何定位问题？ Prolog中有一种通用的调试策略:

If a goal is too general, specialize the program.

我们可以通过添加进一步的目标来专门化该程序，以便上述查询仍然成功。我将添加 false 和一些 (=)/2 目标。 false 特别有趣，因为它消除了整个子句:

?- divisors2(6,[]).range(I,I,[I]) :- I = 6.range(I,K,[I|L]) :- K = 6,   I < K,   I1 is I + 1,   range(I1,K,L).divisors1([],[],X) :- K=6.divisors1([H|T],S,X):- false,   divisors1(T,W,X),   Z is X mod H,   Z=0,   S=[H|W].divisors1([_|T],S,X):- S = [], X = 6,   divisors1(T,S,X).divisors2(X,Result) :- X = 6, Result = [].   range(1,X,Result1),   divisors1(Result1,Result,X).

剩下的部分有些地方太笼统了!事实上divisors1/3的递归规则太笼统了。您的这个新修改的程序称为切片，它是我们原始程序的特化。

有几种方法可以解决这个问题，最简单的方法是添加相应的条件，如下所示:

divisors1([],[],_).divisors1([H|T],S,X):-   divisors1(T,W,X),   0 =:= X mod H,   S=[H|W].divisors1([H|T],S,X):-   divisors1(T,S,X),   0 =\= X mod H.

但是，程序的性能并没有提高。为了看到这一点，我将再次专门研究这个程序:

divisors1([],[],_) :- false.divisors1([H|T],S,X):-   divisors1(T,W,X), false,   0 =:= X mod H,   S=[H|W].divisors1([H|T],S,X):-   divisors1(T,S,X), false,   0 =\= X mod H.

因此:无论 false 后面有什么，该程序都会对列表尝试至少 3 * 2^N 次推断长度N。

通过将递归目标放在最后，我们可以避免这种情况。