时间戳

首页 > 解决方案 > 找到一个数的所有自然除数（使用 Prolog）

prolog - 找到一个数的所有自然除数（使用 Prolog）

问题描述

我想创建一个谓词除数（X，[Y]），如果 X>1 并且 Y 是 X 的所有除数的列表，则该谓词除数（X，[Y]）是从 X 开始并下降到 1 的列表。

我现在的代码如下所示：

divisors(1,[1]).
divisors(X,[Y,Z|Ys]) :- 
    X>0,
    Y is X,
    Y>Z, 
    divides(X,[Z|Ys]).

divides(X,[Y,Z|Ys]) :-
    Y>Z, 
    0 is X mod Y, 
    divides(X,[Z|Ys]).
divides(X,[1]).

但是它有几个问题：

  1. 如果询问列表，prolog 会返回错误（例如 ?-divisors(10,X)。）

  2. ?- 除数（X，[Y]）。其中 [Y] 是一个不完整的除数列表是真的......

Guy Coder 编辑

该答案由 OP 提供，并发布在下面的评论中。

搬到这里让其他人可以看到它。

divisors(X,R) :- 
  X > 1, 
  divisors(X,1,[],R). 

divisors(X,D,R,R):-
  D>X.

divisors(N,D0,R0,R) :-
  divisors_0(N,D0,R0,R1), 
  D is D0 + 1, 
  divisors(N,D,R1,R). 

divisors_0(N,D,R0,[D|R0]) :-
  divides(N,D). 

divisors_0(N,D,R0,R0).

divides(N,D) :-
  0 is N mod D.

Op 还注意到此版本中的一些错误：

  1. 如果我问一个像 (10,[1,2,3]) 这样的错误语句，它不会终止。

  2. 如果我问像 (X, [10,5,2,1]) 这样的语句，它会引发错误。（-> 参数没有充分初始化。）

标签： prolog

解决方案

在 Prolog 中，使用回溯并为同一个查询提出多个解决方案是很常见的。因此，我们可以构造一个谓词，将第二个参数与所有除数统一起来，而不是构造一个除数列表。例如：

divisor(N, D) :-
    between(1, N, D),
    0 is N mod D.

然后产生：

?- divisor(12, N).
N = 1 ;
N = 2 ;
N = 3 ;
N = 4 ;
N = 6 ;
N = 12.

上述算法是一个O(n)算法：我们扫描与我们想要获得除数的项目的值线性的除数。我们可以通过扫描到√n轻松地将其改进为O(√n)，并且每次都会产生除数（当然，如果它是除数）和协除数，例如：

emitco(D, _, D).
emitco(D, C, C) :-
    dif(D, C).

divisor(N, R) :-
    UB is floor(sqrt(N)),
    between(1, UB, D),
    0 is N mod D,
    C is N / D,
    emitco(D, C, R).

这仍然会产生正确的答案，但顺序就像一个收敛的交替序列：

?- divisor(12, N).
N = 1 ;
N = 12 ;
N = 2 ;
N = 6 ;
N = 3 ;
N = 4.

?- divisor(16, N).
N = 1 ;
N = 16 ;
N = 2 ;
N = 8 ;
N = 4 ;
false.

我们可以使用findall/3[swi-doc]或setof/3[swi-doc]获得除数列表。setof/3甚至会对除数进行排序，因此我们可以divisors/2按照以下方式实现divisor/2：

divisors(N, Ds) :-
    setof(D, divisor(N, D), Ds).

例如：

?- divisors(2, N).
N = [1, 2].

?- divisors(3, N).
N = [1, 3].

?- divisors(5, N).
N = [1, 5].

?- divisors(12, N).
N = [1, 2, 3, 4, 6, 12].

?- divisors(15, N).
N = [1, 3, 5, 15].

我们可以使用reverse/2来扭转这个结果。

推荐阅读