에라 토 스테 네스 시브 (Sieve of Eratosthenes Scheme)

Question

저는 시브 오브 에라토스테네스의 구현을 계획에서 찾아 보았습니다. .

대부분의 알고리즘은 정적 끝을 사용하거나 반복을 사용합니다. 이것은 언어 지식에 대한 나의 부족함과 짝을 이루어서 모든 사람들에게 도움을 청했습니다.

하나의 인수 (Sieve까지의 숫자)를 사용하고 재귀 만 사용하며 #t (true) 또는 #f (false)과 함께 숫자의 "cons"목록이있는 시브 (Sieve) 구현이 필요합니다.

그래서 기본적으로 알고리즘과 같은 갈 것이다 :

1. 만들기 목록 2에서 - inputed 수를 각 번호가 통과하고 2 거짓
로 나누어 각 번호를 표시
2. 재귀 참으로 시작하는 단지 소수 사실 표시된 남을 때까지
3. 그런 다음 목록에서 다음 "true"를 숫자로 이동 목록
4. 출력

출력 예 :

> (erat-체 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))))) 

제수의 각 배수가 거짓 인 목록을 반환합니다.

(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)))) 

지금이 작동해야처럼, 나는 그것을 통해 수동으로 세 번 갔어요 것 같다, 나는에 문제가있어 기능입니다,하지만 내가 필요한 반환하지 않는 이유를 알아낼 수 없습니다 . 함수 이름에서 알 수 있듯이

(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))을 전달한 다음 mark-off-multiples을 2로 호출하고 (3.#t)(4.#f)(5.#t)을 반환하고 (2.#t)을 추가합니다. 그런 다음 그 자체가 다시 (3.#t)(4.#f)(5.#t)에 전달하고 (4.#f)(5.#t)를 반환 목록의 CDR 와 마크 오프 배수를 호출하고 목록을 아래로 가고 계속 호출 ...

그때 돌려받을 출력은 모든 trues있는 목록입니다 .

잘하면 내 처지를 이해하는 데 도움이됩니다.