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

として呼び出され(primes 50)、 list を返します(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の句、結果および代替を独自の行に配置します。

(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。停止条件はありません。つまり、これは無限ループです。

もう 1 つのことは、呼び出しによっての値(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!は悪いスタイルと見なされます。ループを表現する標準的な方法の 1 つは、名前付き 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 に答える
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 に答える