4

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

?- 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).我得到了无限循环，屏幕上没有任何内容。

为什么 ？

问候

4

3 回答 3

6

你问为什么你得到一个无限循环的查询divisors2(40,R)。向你解释这一点。唉...

......答案是：不，你没有无限循环！你的程序也会找到答案。它是

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 34。这会敲响警钟吗？无论如何，您的程序存在问题。事实上，有两个相当独立的问题。我们怎样才能找到它们？

也许我们看错了一面。只需返回查询。我们的第一个错误是我们如何使用 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 中有一种通用的调试策略：

如果目标过于笼统，则将程序专门化。

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

?- 除数2（6，[]）。

范围（I，I，[I]）：- I = 6。
范围（I，K，[I|L]）：- K = 6，
   我 < ķ,
   I1 是 I + 1，
   范围（I1，K，L）。

除数1（[]，[]，X）：- K=6。
divisors1([H|T],S,X):- false , 
   divisors1(T,W,X), 
   Z 是 X mod H, 
   Z=0, 
   S=[H|W]。
除数1([_|T],S,X):- S = [], X = 6 ,
   除数1（T，S，X）。

除数2（X，结果）：- X = 6，结果 = []。
   范围（1，X，结果1），
   除数1（结果1，结果，X）。

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

解决这个问题的几种方法，最天真的方法是添加相应的条件，如下所示：

除数1（[]，[]，_）。
除数1（[H|T]，S，X）：-
   除数1（T，W，X），
   0 =:= X mod H,
   S=[H|W]。
除数1（[H|T]，S，X）：-
   除数1（T，S，X），
   0 =\= X 模 H。

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

除数1（[]，[]，_）：-假。
除数1（[H|T]，S，X）：-
   divisors1(T,W,X), false ,
    0 =:= X mod H ,
    S=[H|W]。
除数1（[H|T]，S，X）：-
   除数1(T,S,X), false ,
    0 =\= X mod H。

因此：无论 后面是什么false，这个程序至少会尝试3 * 2^N推断长度列表N。

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

于 2013-01-12T00:27:29.887 回答
4

如果你更正你的范围（对递归结束子句使用一个cut），你会得到它的工作。但是，您不会在找到所有除数后立即成功。

使用您的一般想法的解决方案，但也内置了 /3 和 bagof/3 （使打字更容易）：

divisors(X, Divs) :- bagof(D, divs(X,D), Divs).
divs(X,D) :- between(1,X,D), 0 is X mod D.

请注意，此解决方案按升序返回除数。

于 2013-01-11T08:26:59.807 回答
4

你这里有一个错误

divisors1([H|T],S,X):-
   divisors1(T,W,X),
   Z is X mod H,
   Z==0,S=[H|W]. <=== here

如果 Z 为零，则 S = [H|W] 否则 S = W。

于 2013-01-11T08:27:36.537 回答