序言 - 得到給定數字的因素不會停止？

Question

我需要找到一個給定的數字，e.g的因素：

?- 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

你在這裏

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.

Answer 2

如果你糾正你的範圍（使用結束遞歸的最子句切），你會得到它的排序工作。儘管如此，你並不能立即找到所有的因數。

使用您的總體思路解決方案，但也/ 3和bagof/3之間的內置插件（使打字更容易一點）：

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

請注意，這個解決方案返回遞增的順序的除數。

Answer 3

你會問，爲什麼你的查詢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中有一種通用的調試策略：

如果一個目標太籠統，則需要專門化該程序。

我們可以通過添加更多的目標，使得上面的查詢仍然成功專門的程序。我會加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的列表。

通過遞歸遞歸目標，我們可以避免這種情況。