0

我对 Prolog 的递归函数有疑问。我相信我没有正确实施它，需要帮助。

我需要生成前 N 个素数并将其返回到列表中。生成素数不是问题，而是在列表中生成它是我遇到的问题。

这是相关代码的一部分：

genList(_, 0, _).
genList(X, N, PrimeList, PrimeList):-
    N > 0,
    isprime(X),
    X1 is X +1,
    N1 is N -1,
    genList(X1,N1,[X|PrimeList], [X|PrimeList]),!.
genList(X, N, PrimeList, PrimeList):-
    N>0,
    \+isprime(X),
    X1 is X + 1,
    genList(X1,N,PrimeList, PrimeList).

这是我在 Prolog 解释器中输入的内容：

genList(1,N, [],L).

对于第一行，我如何制作基本情况，以便何时N=0停止递归？它是否正确？

至于接下来的 2 个子句，我在逻辑编程方面难以思考。我绝对觉得这不是逻辑编程风格。

我想说的是，当isPrime(X)失败时，我们继续下一个数字而不保存任何内容，但是当isPrime(X)为真时，我们递归并继续下一个数字，保存X。

我如何在 Prolog 中做到这一点？

4

2 回答 2

3

首先，如果您只需要两个，则您的主要谓词不需要 4 个参数。在这里你想要第一个素数的列表直到N。所以N列表的一个参数和一个参数就足够了：

primeList(N, L) :-
    % eventually in the body a call to a worker predicate with more arguments

现在在这里，用这些术语解释您的逻辑：

primeList(N, [N|L]) :-
    % If we're not at the base case yet
    N > 0,
    % If N is a prime
    isPrime(N),
    NewN is N - 1,
    % Let's recurse and unifie N as the head of our result list in the head
    % of the predicate
    primeList(NewN, L).

primeList(N, L) :-
    % Same as above but no further unification in the head this time.
    N > 0,
    % Because N isn't a prime
    \+ isPrime(N),
    NewN is N - 1,
    primeList(NewN, L).

为此，您必须添加基本案例

primeList(0, []).

您可以通过以下方式重写它：

primeList(0, []) :- !.
primeList(N, [N|L]) :-
    isPrime(N),
    !,
    NewN is N - 1,
    primeList(NewN, L).
primeList(N, L) :-
    NewN is N - 1,
    primeList(NewN, L).
于 2012-09-16T11:45:33.277 回答
2

这是您要写的内容：

genList(N, L) :- genList(2, N, L, []).

genList(X, N, L, Z):-  % L-Z is the result: primes list of length N
    N > 0 ->
      ( isprime(X) -> L=[X|T], N1 is N-1 ; L=T, N1 is N ),
      X1 is X + 1,
      genList(X1,N1,T,Z)
    ;
      L = Z.

if-then-else结构体现了削减。你是对的，它本质上是一种函数式编程风格。

我们可以对其进行一些改动，禁止对 0 素数的请求（无论如何这都没有意义），这样我们也可以取回最后生成的素数：

genList(1, [2], 2) :- !.
genList(N, [2|L], PN) :- N>1, L=[3|_], N2 is N-2, gen_list(N2, L, [PN]).

gen_list(N, L, Z) :- L=[P|_], X is P+2, gen_list(X, N, L, Z).

gen_list(X, N, L, Z) :-  % get N more odd primes into L's tail
    N > 0 ->
      ( isprime(X) -> L=[_|T], T=[X|_], N1 is N-1 ; L=T, N1 is N ),
      X1 is X + 2,
      gen_list(X1,N1,T,Z)
    ;
      L = Z.           % primes list's last node

运行：

?- genList(8,L,P).

L = [2, 3, 5, 7, 11, 13, 17, 19]
P = 19

这也使我们能够从停止的点停止并继续生成素数，而不是从头开始：

?- L = [3|_], gen_list(8, L, Z),    Z=[P10|_],  writeln([2|L]), 
              gen_list(10, Z, Z2),  Z2=[P20],  writeln(Z).

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29|_G1037]
[29,31,37,41,43,47,53,59,61,67,71]

P10 = 29
P20 = 71
于 2012-09-17T05:55:06.873 回答