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).我几乎想用故障切片向你解释这个.唉......

......答案是:不,你没有得到无限循环!而你的程序也找到了答案.它的

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中有一个通用的调试策略:

如果目标过于笼统,请专注于该计划.

我们可以通过添加进一步的目标来专门化该程序,使得上述查询仍然成功.我会补充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.

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