1

次の関数が再帰的にどのように機能するかについて、誰かが説明してくれませんか。(smooth n (- k 1))より単純な再帰的な例は理解できますが、 or ステートメントの下で必要な値がどのように得られるかはわかりません。

(define (divides a b)
  (= (modulo b a) 0))

(define (smooth n k)
  (and (>= k 2)
       (or (divides k n)
           (smooth n (- k 1)))))

(define (isprime p)
  (if (< p 2)
      #f
      (not (smooth p (floor (sqrt p))))))

素数としてisprime使用しない関数を書きましたが、上記の関数がどのように機能するか、この例でどのように機能するかがまだよくわかりません。1

4

3 に答える 3

4

おそらく、次のように書き直すと理解しやすいでしょう。これはsmooth完全に同等の形式ですが、cond代わりにand,を使用しorます。

(define (smooth n k)
  (cond ((< k 2)
         #f)
        ((divides k n)
         #t)
        (else
         (smooth n (- k 1)))))

基本的に、手順は次のように述べています。

  • kが 2 未満の場合、「nスムーズ」ではありません
  • が を正確にk割る場合は、 「スムーズ」ですnn
  • それ以外の場合は、減算1しkて試行を続けます

言い換えればn、それ自体と 1 以外に約数がある場合、それは「滑らか」であると言います。明らかに、数値が素数であるかどうかをテストする手順を書くのは簡単です。その「滑らかさ」の観点からです。数値がより大きく、2滑らかでない場合 (つまり、それ自体と 以外に除数を持たない場合1)は素数です。 . そして、この投稿では、素数かどうかを判断するために、数の平方根までの除数をテストするだけでよい理由を説明しています。

于 2013-09-17T14:48:42.147 に答える
1

それぞれの呼び出しを書き留めてみると理解しやすいです。例えば：

(smooth 5 4)
    (smooth 5 3)
        (smooth 5 2)


(define (smooth 5 3)
   (and (>= 4 2)
        (or (divides 3 5)
            (smooth 5 (- 3 1)))))

(define (smooth 5 2)
   (and (>= 2 2)
        (or (divides 2 5)
            (smooth 5 (- 2 1)))))

(define (smooth 5 1)
   (and (>= 2 1) # This returns false
        #t))

(define (smooth 5 2)
   (and #f #t))

(define (smooth 5 3)
   (and #t #f))

(define (smooth 5 4)
   (and #t #f))

#f
于 2013-09-17T14:49:08.370 に答える
1

smooth n knが2 ～ の約数を持つ場合は true ですk。

実際にはループと同等です：

for i from k to 2 :
    if i divides n, return True
于 2013-09-17T14:52:24.150 に答える