Prolog查找N個素數

我遇到了Prolog遞歸函數的問題。我相信我沒有正確實施，需要幫助。Prolog查找N個素數

我需要生成前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).

對於1號線，如何使基本情況如當N=0，我停止遞歸？它是否正確？

至於接下來的2個子句，我在邏輯編程方面有困難。我絕對認爲這不是邏輯編程風格。

我想說的是，當isPrime(X)失敗了，我們繼續下一個數字，沒有保存任何，但是當isPrime(X)是真的，那麼我們遞歸，繼續下一個號碼，節省X。

如何在Prolog中執行此操作？

來源

2012-09-16 ali

首先，如果你只需要兩個參數，你不應該需要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-16 11:45:33 m09

嘿模！真誠感謝您在代碼中的意見。它幫助我清除了我在解決這個問題時的許多疑問。雖然有關CUT的問題。在第二個條款中，在第二條款 'code'isPrime（N），！， NewN是N-1，'code' 當您到達！時，是否正確地說它會停止在那個謂詞中遞歸，然後繼續下一個（你不測試N是否是素數）？謝謝。 – ali

不，只是意味着選擇點將被刪除。搜索選擇點和切，你應該找到很好的資源:) – m09

@ali與新問題問這個答案我意識到我甚至沒有正確回答你的第一個問題。無論如何，希望你成功地適應了你的問題！ – m09

這裏是你的意思寫：

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-17 05:55:06

Prolog查找N個素數

回答

相關問題