4

所以我对 Prolog 比较陌生，虽然这个问题在许多其他语言中很容易，但我遇到了很多麻烦。我想为数字 N 生成一个因子列表。我已经建立了一个谓词，告诉我一个数字是否是一个因子：

% A divides B
% A is a factor of B
divides(A,B) :- A =\= 0, (B mod A) =:= 0.

% special case where 1 // 2 would be 0
factors(1,[1]) :- !.

% general case
factors(N,L):- N > 0, factor_list(1, N, L).
factor_list(S,E,L) :- S =< E // 2, f_list(S,E,L).

f_list(S,E,[])    :- S > E // 2, !.
f_list(S,E,[S|T]) :- divides(S,E), !, S1 is S+1, f_list(S1, E, T).
f_list(S,E,L)     :- S1 is S+1, f_list(S1,E,L).

任何帮助，将不胜感激。

编辑

我几乎改变了我的整个解决方案，但由于某种原因factors(9, [1])，当我只想返回 true 时，谓词如 return factors(9, [1,3])true。有什么想法吗？

4

3 回答 3

1

原因factors(9,[1])如下：尝试实例化（即统一）的时机已关闭：

f_list(S,E,[])    :- S > E // 2, !.
f_list(S,E,[S|T]) :- divides(S,E), !, S1 is S+1, f_list(S1, E, T).
f_list(S,E,L)     :- S1 is S+1, f_list(S1,E,L).

%%  flist(1,9,[1]) -> (2nd clause) divides(1,9), S1 is 2, f_list(2,9,[]).
%%  flist(2,9,[])  -> (3rd clause) S1 is 3, f_list(3,9,[]).
%% ... 
%%  flist(5,9,[])  -> (1st clause) 5 > 9 // 2, !.

因为您预先指定[1]了 ，所以当它达到 3 时，尾部是[]并且与第二个子句的匹配由此被阻止，尽管它会由于 . 而成功divides/2。

解决方案是将统一从子句的头部移到正文中，并且仅在适当的时间而不是更早地进行：

f_list(S,E,L) :- S > E // 2, !, L=[].
f_list(S,E,L) :- divides(S,E), !, L=[S|T], S1 is S+1, f_list(S1, E, T).
f_list(S,E,L) :- S1 is S+1, f_list(S1,E,L).

上面通常是用 if-else 结构编写的：

f_list(S,E,L) :- 
  ( S > E // 2   -> L=[]
  ; divides(S,E) -> L=[S|T], S1 is S+1, f_list(S1, E, T)
  ;                          S1 is S+1, f_list(S1, E, L)
  ).

您也可以将主要谓词简化为

%% is not defined for N =< 0
factors(N,L):- 
  (  N =:= 1 -> L=[1]
  ;  N >= 2  -> f_list(1,N,L) 
  ).
于 2013-03-31T20:24:04.157 回答
1

就个人而言，我使用了一个看起来更简单的解决方案：

factors(1,[1]):- true, !.
factors(X,[Factor1|T]):- X > 0,
 between(2,X,Factor1), 
 NewX is X // Factor1, (X mod Factor1) =:= 0,
 factors(NewX,T), !.

这个只接受一个有序的因素列表。

于 2013-09-07T23:10:14.950 回答
1

这是一个简单的基于枚举的过程。

factors(M, [1 | L]):- factors(M, 2, L).
factors(M, X, L):- 
   residue(M, X, M1), 
   ((M==M1, L=L1); (M1 < M, L=[X|L1])),
   ((M1=1, L1=[]); (M1 > X, X1 is X+1, factors(M1, X1, L1))).

residue(M, X, M1):-
  ((M < X, M1=M);
   (M >=X, MX is M mod X, 
     (MX=0, MM is M/X, residue(MM, X, M1);
      MX > 0, M1=M))).
于 2014-07-20T15:25:06.920 回答