0

2 から任意の数 n までの素数のリストを作成する手順を作成しようとしています。もちろん、これは繰り返し行う必要がありますが、何が間違っているのか正確にはわかりません。

(define (list-2-to-n n)
    (define (iter n result)
        (if (= n 0)
            result
        (if (< n 2)
           '()
            (if (= (remainder n 3) 0)
                (list-2-to-n (- n 1))
            (if (even? n)
                (list-2-to-n (- n 1))
                (iter (- n 1) (cons n result)))))))

    (iter n '()))

テストケースがプロシージャを通過するたびに、常に戻ります()

4

1 に答える 1

1

私が間違っていること。

どれどれ。まず第一に、あなたのインデントはひどく誤解を招くものです。コードの構造を正しく反映する必要があります。

(define (list-2-to-n-0 n)       ; a global function
    (define (iter n result)     ; an internal function
        (if (= n 0)             
            result
            (if (< n 2)                        ; **else**
               '()
                (if (= (remainder n 3) 0)
                    (list-2-to-n (- n 1))
                    (if (even? n)              ; **else**
                        (list-2-to-n (- n 1))
                        (iter (- n 1) (cons n result)))))))
    (iter n '()))

そうでない場合は、少なくとも代替条項にコメントを付けて明確にマークする必要があります。

ここで、入力数値が 2 または 3 で割り切れるかどうかをテストし、まったく同じ方法で応答します。2 つのケースは実際に 1 つに結合する必要があります。また、condネストされた多数ifの s の代わりに、ここで使用できます。

(define (list-2-to-n-1 n)       ; a global function 
    (define (iter n result)     ; an internal function
        (cond
            ((= n 0)  result)
            ((< n 2)  '())
            ((or (= (remainder n 2) 0) (= (remainder n 3) 0))
              (list-2-to-n (- n 1))       ; calling a global function, and
            (else                         ;   returning its result
              (iter (- n 1)               ; calling internal function, and
                    (cons n result)))))   ;   returning its result
    (iter n '()))

そこでグローバル関数を呼び出すということは、プロセス全体を新たに開始することを意味します iter。最初のアキュムレータ引数(). ケースが最初に遭遇し、返されるため（正確に観察された動作）、0を超える初期値の場合、結果を返すと思われるケースn==0は実際には到達できません。nn < 2()

新たに開始しないでください。つまり、常に内部関数を呼び出す必要があります。基本ケースを修正する必要があります。最後になりましたが、2 または 3 で割り切れるかどうかをチェックするだけでは十分ではありません。すでに 5 ですisPrime。

(define (list-2-to-n-1 n)       ; a global function
    (define (iter n result)     ; an internal function
        (cond
            ((< n 2)  result)
            ((not (isPrime n))
              (iter (- n 1) result))      ; calling internal function, without
            (else                         ;   altering the accumulator
              (iter (- n 1)               ; calling internal function, 
                    (cons n result)))))   ;   altering the accumulator
    (iter n '()))

isPrime2、3、... で割るn必要があります。2 を超える偶数で割る必要はありません。オッズだけで十分です。dのような潜在d * d > n的な除数n = f * d, f <= dを試す必要はありません。f*d <= d*dn <= d*d

もちろん、9、15、77 などの合成による除算も不要です。これらのいずれかが除算された場合、nそれらの素因数 3、5、7、11 のいずれかでも除算され、それらをより早く検出できます。実際には、素数だけで割ってみるだけで十分です。それを可能にするには、コードを再構築して、素数の結果のリストを昇順で構築し、sqrt(k)各候補をテストするために以下のプレフィックス部分を使用するようにする必要がありますk。

これは試行分割アルゴリズムとして知られています。次に、エラトステネスのはるかに高速なふるいがあります。

于 2013-10-31T09:08:36.643 に答える