prolog - 数的因数

Question

所以我对 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，当我只想要 factors(9, [1,3]) 时返回真。有什么想法吗？

Answer 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) 
  ).