Das finden einer Primzahl im Schema mit natürlichen Rekursion

Ich bin immer noch einstecken Weg bei den übungen, Wie man in den Design-Programme auf meinem eigenen, aber haben es geschafft, wieder stecken. Dieses mal ist es die Frage 11.4.7:

Entwickeln Sie die Funktion
ist-nicht-teilbar-durch<=ich. Es verbraucht
Natürliche Zahl [>=1], ich, und eine Natürliche
Anzahl m, mit i < m,. Falls m nicht
teilbar durch eine Zahl zwischen 1
(exklusive) und ich (inclusive), die
Funktion liefert true, andernfalls, seine
die Ausgabe ist false.

Verwenden ist-nicht-teilbar-durch<=i zu definieren
prime?, das verbraucht eine Natürliche
Anzahl und bestimmt, ob oder nicht
es ist eine Primzahl.

Den ersten Teil hatte ich nicht zu hart mit:

;; A natural number [>=1] is either 1. 1 or 
;; 2. (add1 n) where n is a natural number [>=1].

;; is-not-divisible-by<=i : N[>=1] N -> boolean
(define (is-not-divisible-by<=i i m)
  (cond
    [(= i 1) true]
    [else (cond
            [(= (remainder m i) 0) false]
            [else (is-not-divisible-by<=i (sub1 i) m)])]))
(is-not-divisible-by<=i 3 6) ; expected: false.
(is-not-divisible-by<=i 6 7) ; expected: true.

Aber ich kann einfach nicht sehen, wie kann ich eine variable verwenden, um dies zu tun, während mit den natürlichen Rekursion. Ich dachte über die Verwendung einer Liste, aber, das zeigt die gleichen Probleme.

Die einzige Lösung, die ich sehen kann, ist mit dem weiteren Variablen-sagen wir x-der gleiche Wert wie n, und dann, es einfach zu tun die Art und Weise ist-nicht-teilbar-durch<=ich kann es. Aber ich denke, die Autoren wollen für mich, es zu tun einige andere, einfachere Möglichkeit. (Und ich weiß gar nicht, wie das zu tun, was ich beschrieben sowieso, haha.)

Dieses problem hat wirklich Zerschlagung meinen Hintern, so dass jede Hilfe oder Hinweise, wenn Sie könnte, wäre toll!

InformationsquelleAutor James Callaway | 2010-07-27
  1. 3

    Eine Primzahl ist eine Zahl, die nicht geteilt werden kann durch jede Zahl kleiner als Sie selbst. Haben Sie bereits umgesetzt ", kann nicht geteilt werden, indem eine beliebige Anzahl kleiner als" Teil:

    (define (prime? n)
  (is-not-divisible-by<=i (sub1 n) n))
    • Oh, jeeze, das ist peinlich. Ich dachte die ganze Zeit, dass, wenn ich wusste, dass der Wert von n ist, würden weiterhin fallen, jedes mal, wenn die Funktion rekursiv aufgerufen. Ich glaube nicht, dass (sub1 n) würde behandelt werden wie ein x, aber wie ein n, das macht nicht viel Sinn. Vielen Dank!
    • Es ist alles eine Frage, ob Sie denken, in Bezug auf die Werte (kann nicht geändert werden) oder Variablen (kann geändert werden)... nicollet.net/2010/01/quick-test 😉
    InformationsquelleAutor Victor Nicollet
  2. 1

    (prime? 1) bekommt ein "division durch null" - Fehler.

    hier ist eine modifizierte version der original-code. Es kümmert sich um (prime? 1) problem für jetzt.

    (define (prime? p)
  (define (non-divisible-by n d)
    (cond
     ((= d 1) #t)
     (else (if(= (remainder n d) 0)
          #f
          (non-divisible-by n (- d 1))))))
  (if (= p 1)
      #t
      (non-divisible-by p (- p 1))))

    Nun (prime? 1) liefert #t

    • Beachten Sie, dass sollten Sie wieder #f im Fall von 1, 1 ist nicht prim.
    InformationsquelleAutor joe
  3. 0

    Ist es nicht notwendig, dass Sie teilen alle zahlen von n-1 bis 2 zu überprüfen primality. Sie brauchen nur zu überprüfen (floor (sqrt n)). So ist eine schnellere Zufahrt (speziell für große zahlen), die kümmert sich auch über die unbestimmten (prime? 1) problem ist:

    (define (prime? n)
  (is-not-divisible-by<=i (floor (sqrt n)) n))
    InformationsquelleAutor Sergio Maass
Schreibe einen Kommentar