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の推論を必要としました。これは、234未満です。これはベルを鳴らしますか？いずれにせよ、プログラムに問題があります。実際、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には1つの一般的なデバッグ戦略があります：

目標が一般的すぎる場合は、プログラムを専門化します。

上記のクエリが引き続き成功するように、さらに目標を追加することで、プログラムを特殊化できます。falseといくつかの(=)/2目標を追加します。false句全体が消去されるため、特に興味深いものです。

？-divisors2（6、[]）。

range（I、I、[I]）：- I=6。
range（I、K、[I | L]）：- K = 6、
   I <K、
   I1はI+1です
   range（I1、K、L）。

divisors1（[]、[]、X）：- K=6。
divisors1（[H | T]、S、X）：- false、
   divisors1（T、W、X）、
   ZはX mod H、
   Z = 0、
   S = [H|W]です。
divisors1（[_ | T]、S、X）：- S = []、X = 6、
   divisors1（T、S、X）。

divisors2（X、Result）：- X = 6、結果=[]。
   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 = \ =XmodH。

ただし、プログラムのパフォーマンスは向上しませんでした。これを見るために、私は再びこのプログラムを専門にします：

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 = \ = XmodH。

したがって、の背後に何があるかに関係なくfalse、このプログラムは少なくとも3 * 2^N長さのリストに対して推論を試みNます。

再帰的な目標を最後に置くことで、これを回避できます。

于 2013-01-12T00:27:29.887 に答える
4

範囲を修正すると（再帰の終わりの句にカットを使用）、ある程度機能するようになります。ただし、すべての除数を見つけてもすぐには成功しません。

一般的な考え方だけでなく、組み込みの/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 に答える