recursion - 埃拉托色尼筛法

Question

我一直在网上搜索 Eratosthenes 筛法在 scheme 中的实现，虽然我想出了很多内容，但似乎没有一个符合我的需要。

问题是大多数算法要么使用静态结束，要么使用迭代。这再加上我对语言知识的缺乏导致我向你们所有人寻求帮助。

我需要一个 Sieve 的实现，它接受一个参数(Sieve until 的数字)，仅使用递归并具有一个带有 #t (true) 的数字的“缺点”列表或 #f(假)。

所以基本上算法会这样进行:

1. 从 2 开始列出 - 输入数字，每个数字都以 true 开头
2. 递归遍历并标记每个可被 2 整除的数字 false
3. 然后继续处理列表中的下一个“真”数，直到只留下标记为真的素数
4. 输出列表

示例输出:

> (erat-sieve 20)

((2 . #t) (3 . #t) (4 . #f) (5 . #t) (6 . #f) (7 . #t) (8 . #f) (9 . #f) (10 . #f) (11 . #t) (12 . #f) (13 . #t) (14 . #f) (15 . #f) (16 . #f) (17 . #t) (18 . #f) (19 . #t) (20 . #f))

如果您也能提供评论来彻底解释代码，那将不胜感激。

谢谢!

修订::: 所以我学到了一些方案来进一步解释我的问题......

这就是列表。

(define (makeList n)
 (if (> n 2)
  (append (makeList (- n 1)) (list (cons n (and))))
  (list (cons 2 (and)))))

这将返回一个列表，其中每个除数的倍数都标记为 false。

(define (mark-off-multiples numbers divisor)
 (if (null? numbers)
  '()
  (append 
     (list (cons (car (car numbers)) 
                 (not (zero? (modulo (car (car numbers)) divisor))))) 
     (mark-off-multiples (cdr numbers) divisor))))

现在这是我遇到问题的功能，它似乎应该可以工作，我已经手动检查了它 3 次，但我不明白为什么它没有返回我需要的东西。

(define (call-mark-off-multiples-for-each-true-number numbers)
 (if (null? numbers)
  '()
  (if (cdr (car numbers))
    (append (list (car numbers))
            (call-mark-off-multiples-for-each-true-number 
               (mark-off-multiples (cdr numbers) (car (car numbers)))))
    (append (list (car numbers))
            (call-mark-off-multiples-for-each-true-number 
               (cdr numbers))))))

正如函数名称所暗示的那样，我试图让它做的是，为列表中仍标记为真的每个数字调用标记乘数。所以你传入 ((3.#t)(4.#t)(5.#t)) 然后它为 2 调用 mark-off-multiples 和返回 (3.#t)(4.#f)(5.#t) 并向其附加 (2.#t)。然后它再次调用自身传入 (3.#t)(4.#f)(5.#t) 并使用 cdr 调用 mark-off-multiples列表返回 (4.#f)(5.#t) 并继续在列表中向下移动...

然后我返回的输出是一个包含所有真值的列表。

这，希望能帮助你更好地理解我的困境。

Answer 1

这是一个有效的解决方案。

(define (divides? m n)
  (if (eq? (modulo n m) 0)
      #t
      #f))

(define (mark-true n)
  (cons n #t))

(define (mark-divisors n ns)
  (cond ((null? ns) '())
        ((and (unmarked? (car ns)) 
              (divides? n (car ns))) 
           (cons (cons (car ns) #f) (mark-divisors n (cdr ns))))
        (else (cons (car ns) (mark-divisors n (cdr ns))))))

(define (unmarked? n)
  (not (pair? n)))

(define (eratosthenes x)
  (cond ((null? x) '())
        ((unmarked? (car x)) 
           (cons (mark-true (car x)) 
                 (eratosthenes (mark-divisors (car x) (cdr x)))))
        (else (cons (car x) (eratosthenes (cdr x))))))

(eratosthenes (list 2 3 4 5 6))

我已经使用了许多辅助函数，但如果需要，您可以将它们添加到 eratosthenes 函数中。我认为这使整个业务更具可读性。

mark-true 将一个值放在 #t 上。 mark-divisors 接受一个数字 n 和一个数字列表，并将所有被 n 划分的数字包含在一个 #f。几乎所有其他内容都是不言自明的。 Eratosthenes 正常工作，如果第一个数字是“未标记”，它将其标记为“真”或“素数”，然后从列表的其余部分“划掉”它的所有倍数，然后对每个后续的“未标记”重复列表中的数字。我的 eratosthenes 函数基本上完成了您尝试对您的函数执行的操作。我不确定你的问题是什么，但通常来说，让助手让你的东西更具可读性是有帮助的。

我在 DrRacket 中使用 Neil Van Dyke 的 SICP 包完成了这项工作。我不知道你用的是什么方案。如果您在使用它时遇到问题，请告诉我。