3

私はエラトステネスのふるいをスキームで実装するためにウェブを検索してきました、そして私はたくさんのコンテンツを思いついたけれども、それらのどれも私がそれをする必要があるようにそれを成し遂げたようには見えませんでした。

問題は、ほとんどのアルゴリズムが静的終了を使用するか、反復を使用することです。これは私の言語の知識の欠如と相まって、私はあなた方全員に助けを求めるようになりました。

1つの引数（Sieveまでの数値）を取り、再帰のみを使用し、#t（true）または#f（false）の数値の「短所」のリストを持つSieveの実装が必要です。

したがって、基本的にアルゴリズムは次のようになります。

  1. 2からリストを作成-入力された番号。各番号はtrueから始まります
  2. 再帰的に調べて、2で割り切れる各数値にfalseをマークします。
  3. 次に、素数だけがtrueとマークされるまで、リスト内の次の「true」番号に進みます。
  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))))))

私がやろうとしているのは、関数名が示すように、リストの下でまだtrueとマークされている番号ごとにmark-off-multiplesを呼び出すことです。したがって、パスしてから2を((3.#t)(4.#t)(5.#t))呼び出しmark-off-multiplesて戻り(3.#t)(4.#f)(5.#t)、それに追加(2.#t)します。次に、それ自体が再び渡され(3.#t)(4.#f)(5.#t)、マークオフ倍数が呼び出され、リストのcdrが返さ(4.#f)(5.#t)れ、リストを下に移動し続けます...

次に返される出力は、すべてtrueのリストです。

これは、うまくいけば、私の苦境をよりよく理解するのに役立ちます。

4

4 に答える 4

2

これが機能するソリューションです。

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

私はいくつかのヘルパー関数を使用しましたが、必要に応じてそれらをエラトステネス関数に追加することができます。このビジネス全体が読みやすくなると思います。

mark-trueに値を割り当てます#t。mark-divisors数と数のリストを取り、に分割されるnすべての数を含みます。他のほとんどすべては自明です。エラトステネスは正常に機能します。最初の桁が「マークされていない」場合は、「真」または「素数」としてマークされ、リストの残りの部分からすべての倍数を「取り消し」てから、後続の「マークされていない」ごとに繰り返されます。リストの数字。私のエラトステネス機能は、基本的にあなたがあなたのものでやろうとしていたことをします。あなたの問題が何であるかはわかりませんが、原則として、あなたのものをより読みやすくするためにヘルパーを作ることは役に立ちます。n#f

これは、DrRacketでNeilVanDykeのSICPパッケージを使用して行いました。使用しているスキームがわかりません。これを機能させるのに問題がある場合はお知らせください。

于 2012-03-30T04:42:12.260 に答える
1

さて、SoEのポイントは、除算性をテストすることではなく、一度にp個ずつ数えることです。

(define (make-list n)              ; list of unmarked numbers 2 ... n
  (let loop ((i n) 
             (a '()))
    (if (= i 1)
      a            ; (cons '(2 . #t) (cons (3 . #t) ... (list '(n . #t))...))
      (loop (- i 1) (cons (cons i #t) a)))))

(define (skip2t xs)                ; skip to first unmarked number
  (if (cdar xs) xs (skip2t (cdr xs))))

(define (mark-each! k n i xs)      ; destructive update of list xs - 
  (set-cdr! (car xs) #f)           ;  mark each k-th elem,
  (if (<= (+ i k) n)               ;  head is i, last is n 
    (mark-each! k n (+ i k)
                    (list-tail xs k))))

(define (erat-sieve n)
  (let ((r  (sqrt n))              ; unmarked multiples start at prime's square
        (xs (make-list n)))
    (let loop ((a xs))
      (let ((p (caar a)))          ; next prime
        (cond ((<= p r)
               (mark-each! p n (* p p) (list-tail a (- (* p p) p)))
               (loop (skip2t (cdr a)))))))
    xs))

となることによって(erat-sieve 20) ==> ((2 . #t) (3 . #t) (4) (5 . #t) (6) (7 . #t) (8) (9) (10) (11 . #t) (12) (13 . #t) (14) (15) (16) (17 . #t) (18) (19 . #t) (20))

式に従う無制限のふるい

      P = {3,5,7,9、...} \ U {{ p 2、p 2 + 2p、p 2 + 4p、p 2 + 6p、...} | p in P }

SICPスタイルのストリームを使用して定義できます（ここで確認できます）。

 ;;;; Stream Implementation
 (define (head s) (car s))
 (define (tail s) ((cdr s))) 
 (define-syntax s-cons
   (syntax-rules () ((s-cons h t) (cons h (lambda () t))))) 

 ;;;; Stream Utility Functions
 (define (from-By x s)
   (s-cons x (from-By (+ x s) s)))
 (define (take n s) 
   (cond ((= n 0) '())
         ((= n 1) (list (car s)))
         (else (cons (head s) (take (- n 1) (tail s))))))
 (define (drop n s)
   (cond ((> n 0) (drop (- n 1) (tail s)))
         (else s)))
 (define (s-map f s)
   (s-cons (f (head s)) (s-map f (tail s))))
 (define (s-diff s1 s2)
   (let ((h1 (head s1)) (h2 (head s2)))
    (cond
     ((< h1 h2) (s-cons h1 (s-diff  (tail s1)       s2 )))
     ((< h2 h1)            (s-diff        s1  (tail s2)))
     (else                 (s-diff  (tail s1) (tail s2))))))
 (define (s-union s1 s2)
   (let ((h1 (head s1)) (h2 (head s2)))
    (cond
     ((< h1 h2) (s-cons h1 (s-union (tail s1)       s2 )))
     ((< h2 h1) (s-cons h2 (s-union       s1  (tail s2))))
     (else      (s-cons h1 (s-union (tail s1) (tail s2)))))))

 ;;;; odd multiples of an odd prime
 (define (mults p) (from-By (* p p) (* 2 p)))

 ;;;; The Sieve itself, bounded, ~ O(n^1.4) in n primes produced
 ;;;;   (unbounded version runs at ~ O(n^2.2), and growing worse)
 ;;;;   **only valid up to m**, includes composites above it        !!NB!!
 (define (primes-To m)
   (define (sieve s) 
    (let ((p (head s))) 
     (cond ((> (* p p) m) s) 
      (else (s-cons p 
              (sieve (s-diff (tail s) (mults p))))))))
   (s-cons 2 (sieve (from-By 3 2))))

 ;;;; all the primes' multiples, tree-merged, removed; 
 ;;;;    ~O(n^1.17..1.15) time in producing 100K .. 1M primes
 ;;;;    ~O(1) space (O(pi(sqrt(m))) probably)
 (define (primes-TM)
   (define (no-mults-From from)
       (s-diff (from-By from 2) (s-tree-join (s-map mults odd-primes))))
   (define odd-primes 
       (s-cons 3 (no-mults-From 5)))
   (s-cons 2 (no-mults-From 3)))

 ;;;; join an ordered stream of streams (here, of primes' multiples)
 ;;;; into one ordered stream, via an infinite right-deepening tree
 (define (s-tree-join sts)                               ;; sts -> s
   (define (join-With of-Tail sts)                       ;; sts -> s
     (s-cons (head (head sts))
              (s-union (tail (head sts)) (of-Tail (tail sts)))))
   (define (pairs sts)                                   ;; sts -> sts
     (s-cons (join-With head sts) (pairs (tail (tail sts)))))
   (join-With (lambda (t) (s-tree-join (pairs t))) sts))

 ;;;; Print 10 last primes from the first thousand primes
 (begin 
   (newline)
   (display (take 10 (drop 990 (primes-To 7919)))) (newline)
   (display (take 10 (drop 990 (primes-TM)))) (newline))

MITスキームでテスト済み。

于 2012-08-24T14:43:37.050 に答える
1 
(define (prime-sieve-to n)
  (let* ((sz (quotient n 2)) (sv (make-vector sz 1)) (lm (integer-sqrt n)))
    (for ((i (in-range 1 lm))) 
      (cond ((vector-ref sv i)
        (let ((v (+ 1 (* 2 i))))
          (for ((i (in-range (+ i (* v (/ (- v 1) 2))) sz v)))
            (vector-set! sv i 0))))))
    (cons 2
          (for/list ((i (in-range 1 sz)) 
                     #:when (and (> (vector-ref sv i) 0) (> i 0)))
                    (+ 1 (* 2 i))))))

これは、1億まで機能するスキームのラケット方言のもう1つです。その上、私はその効率を保証しません。

于 2013-05-18T22:09:22.067 に答える
0

コードと説明は、SICP 3.5.2InfiniteStreamshttp://mitpress.mit.edu/sicp/full-text/book/book-ZH-24.html#%_sec_3.5.2にあります 。

于 2012-03-29T07:21:00.477 に答える