2

这可能是一个基本的问题，但我在使用 Scheme 编写的程序时遇到了麻烦。该过程应返回小于或等于 N 的所有素数（N 来自输入）。

(define (isPrimeHelper x k)
  (if (= x k) #t
  (if (= (remainder x k) 0) #f
      (isPrimeHelper x (+ k 1)))))

(define ( isPrime x )
    (cond
      (( = x 1 ) #t)
      (( = x 2 ) #t)
      ( else (isPrimeHelper x 2 ) )))

(define (printPrimesUpTo n)
    (define result '())
    (define (helper x)
        (if (= x (+ 1 n)) result
        (if (isPrime x) (cons x result) ))
        ( helper (+ x 1)))
    ( helper 1 ))

我对主要作品的检查，但该功能printPrimesUpTo似乎永远循环。基本上这个想法是检查一个数字是否是素数并将其放入结果列表中。

谢谢 ：）

4

5 回答 5

3

您有几处错误，并且您的代码非常不习惯。首先，数字 1 不是素数；事实上，它既不是素数也不是合数。其次，result变量并没有像你想象的那样做。第三，你的使用if到处都是不正确的；if是一个表达式，而不是一些其他编程语言中的语句。而且，作为一种风格，右括号堆叠在行尾，并且不占用自己的一行。你需要和你的教授或助教谈谈，以澄清对 Scheme 的一些基本误解。

找到小于n的素数的最佳算法是埃拉托色尼筛法，大约 22 世纪前由一位希腊数学家发明，他发明了闰日和经纬度系统，精确测量了地球的周长和距离从地球到太阳，是亚历山大托勒密图书馆的首席图书管理员。这是他算法的一个简单版本：

(define (primes n)
  (let ((bits (make-vector (+ n 1) #t)))
    (let loop ((p 2) (ps '()))
      (cond ((< n p) (reverse ps))
            ((vector-ref bits p)
              (do ((i (+ p p) (+ i p))) ((< n i))
                (vector-set! bits i #f))
              (loop (+ p 1) (cons p ps)))
            (else (loop (+ p 1) ps))))))

调用 as (primes 50)，返回列表(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)。正如您尝试做的那样，它比通过试除法测试素数要快得多。如果必须，这里有一个适当的素数检查器：

(define (prime? n)
  (let loop ((d 2))
    (cond ((< n (* d d)) #t)
          ((zero? (modulo n d)) #f)
          (else (loop (+ d 1))))))

两种算法都可以进行改进。如果你有兴趣，我谦虚地在我的博客上推荐这篇文章。

于 2012-12-09T23:40:52.597 回答
2

(if)您函数中的(helper)表达式不是函数的尾部表达式，因此不会返回，但控制将始终继续(helper (+ x 1))并递归。

于 2012-12-09T19:49:54.127 回答
2

首先，用缩进来表达嵌套结构是一种很好的风格，所以视觉上很明显；并且还要将if's 的每个子句，即consequent和 the alternative，放在它自己的行上：

(define (isPrimeHelper x k)
  (if (= x k) 
      #t                           ; consequent
      (if (= (remainder x k) 0)    ; alternative
  ;; ^^ indentation
          #f                               ; consequent
          (isPrimeHelper x (+ k 1)))))     ; alternative

(define (printPrimesUpTo n)
    (define result '())
    (define (helper x)
        (if (= x (+ 1 n)) 
            result                  ; consequent
            (if (isPrime x)         ; alternative
                (cons x result) ))         ; no alternative!
        ;; ^^ indentation
        ( helper (+ x 1)))
    ( helper 1 ))

现在可以清楚地看到，您的函数所做的最后一件事就是始终使用递增的值helper调用自身。x没有停止条件，即这是一个无限循环。

另一件事是，调用(cons x result)不会result以任何方式改变 ' 值。为此，您需要设置它，如下所示(set! result (cons x result))：您还需要将此表达式放在一个begin组中，因为它不是根据其值进行评估，而是根据其副作用进行评估：

    (define (helper x)
        (if (= x (+ 1 n)) 
            result        
            (begin 
                (if (isPrime x) 
                    (set! result (cons x result)) )   ; no alternative!
                (helper (+ x 1)) )))

通常，显式使用set!被认为是不好的风格。表达循环的一种标准方法是使用命名 let的尾递归代码，通常使用规范名称“ ”（但它可以是任何名称）：loop

(define (primesUpTo n) 
  (let loop ((x n) 
             (result '())) 
    (cond 
      ((<= x 1) result)      ; return the result
      ((isPrime x) 
            (loop (- x 1) (cons x result)))   ; alter the result being built
      (else (loop (- x 1) result)))))         ; go on with the same result

在存在尾调用优化的情况下，它实际上等同于以前的版本。

于 2012-12-10T16:41:51.987 回答
2

更有效prime?的（来自 Sedgewick 的“算法”）：

(define (prime? n)
  (define (F n i) "helper"
    (cond ((< n (* i i)) #t)
          ((zero? (remainder n i)) #f)
          (else
           (F n (+ i 1)))))
 "primality test"
 (cond ((< n 2) #f)
     (else
      (F n 2))))
于 2017-04-22T23:50:33.103 回答
1

你可以做得更好。我重新编写了您的代码：

(define (prime? x)
  (define (prime-helper x k)
    (cond ((= x k) #t)
          ((= (remainder x k) 0) #f)
          (else
           (prime-helper x (+ k 1)))))
  (cond ((= x 1) #f)
        ((= x 2) #t)
         (else
          (prime-helper x 2))))

(define (primes-up-to n)
  (define (helper x)
    (cond ((= x 0) '())
          ((prime? x)
           (cons x (helper (- x 1))))
          (else
           (helper (- x 1)))))
  (reverse
    (helper n)))

scheme@(guile-user)> (primes-up-to 20)
$1 = (2 3 5 7 11 13 17 19)

请不要像 C 或 Java 那样编写 Scheme ——为了便于阅读，请查看 lisp 系列语言的这些样式规则：不要使用驼峰式大小写，不要将括号放在自己的行上，用标记谓词?，注意正确的缩进，不要在括号内添加额外的空格。

于 2012-12-09T20:30:12.530 回答