使用自然遞歸在Scheme中查找素數

我仍然在自己設計程序的練習中插入，但又設法再次卡住了。這一次，它的問題11.4.7：使用自然遞歸在Scheme中查找素數

的是 - 不除盡，<開發功能 =我。它消耗了自然數[> = 1] i和自然數，其中i爲< m。如果m不是可被1 （不包括）和i（包括）之間的任何數字整除，則函數會生成true;否則，其輸出是錯誤的。

使用是-未除盡-由< = i到限定素？，這消耗了自然數和確定是否不它是素數。

我沒有太多苦時間第一部分：

;; A natural number [>=1] is either 1. 1 or 
;; 2. (add1 n) where n is a natural number [>=1]. 

;; is-not-divisible-by<=i : N[>=1] N -> boolean 
(define (is-not-divisible-by<=i i m) 
    (cond 
    [(= i 1) true] 
    [else (cond 
      [(= (remainder m i) 0) false] 
      [else (is-not-divisible-by<=i (sub1 i) m)])])) 
(is-not-divisible-by<=i 3 6) ; expected: false. 
(is-not-divisible-by<=i 6 7) ; expected: true.

但我只是不明白我怎麼可以使用一個變量，而使用天然遞歸來做到這一點。我想過使用一個列表，但是也出現了相同的問題。

我能看到的唯一解決辦法是給出另一個變量 - 讓我們假設x--與n相同的值，然後按照這種方式是不可分割的 - < =我這樣做。但我認爲作者打算讓我以其他更簡單的方式做到這一點。（而且我甚至不知道該怎麼做我所描述的東西，哈哈。）

這個問題確實是在破壞我的屁股，所以如果可以的話，任何幫助或提示都會很棒！

來源

2010-07-27 James Callaway

素數是一個數字，不能被小於自身的任何數字除。您已經實施了「不能被任何小於」的部分：

(define (prime? n) 
    (is-not-divisible-by<=i (sub1 n) n))

來源

2010-07-27 16:29:10

哦，jeeze，這很尷尬。我認爲，如果我這樣做了，那麼每次函數被遞歸調用時，兩個n的值都會繼續下降1。我不認爲（sub1 n）會被當作一個x來處理，但是作爲一個n，它根本沒有什麼意義。非常感謝！ – 2010-07-27 16:33:41

這完全取決於你是否按照數值（不能改變）或變量（可以改變）來考慮...... http://www.nicollet.net/2010/01/quick-test/;） – 2010-07-27 16:39:06

（prime？1）得到「除零」的錯誤。

這裏是原始代碼的修改版本。它現在需要處理（首要？1）問題。

(define (prime? p) 
    (define (non-divisible-by n d) 
    (cond 
    ((= d 1) #t) 
    (else (if(= (remainder n d) 0) 
      #f 
      (non-divisible-by n (- d 1)))))) 
    (if (= p 1) 
     #t 
     (non-divisible-by p (- p 1))))

現在（質數？1）返回#T

來源

2011-06-23 17:26:11 joe

請注意，如果是1，您應該返回'＃f'，因爲1不是素數。 – blubberdiblub 2017-04-23 09:34:37

這不是必要的，你把所有的數字從正1至2檢查素性。你只需要從（floor（sqrt n））中檢查。所以一個更快的aproach（特別是大數字），也需要關心未定義（prime？1）問題，是：

(define (prime? n) 
    (is-not-divisible-by<=i (floor (sqrt n)) n))

來源

2013-03-16 16:13:23

使用自然遞歸在Scheme中查找素數

回答

相關問題