SOLVIUM

Programmierung

Primfaktorzerlegung in tScheme

Der Code

Der folgende Code zur Primfaktorzerlegung einer Zahl ist hochgradig imperativ. Es gibt auch die Möglichkeit, die Primfaktorzerlegung rekursiv zu implementieren, den folgenden Algorithmus haben wir so aber auch in Java umgesetzt.

(define (primfaktoren n)
  (let
    faktoren nil
    i 2
    (seq
      (while (<= i n)
        (if (= (mod n i) 0)
          (seq
            (set faktoren (concat faktoren (list i)))
            (set n (/ n i))
            (set i 2)
          ) ; seq
        (set i (+ i 1)))
      ) ; while
      faktoren
    ))) ; seq ; let ; define

Die Funktionsweise

Wir definieren per let die lokalen Variablen factors und i. factors soll die Primfaktoren enthalten und wird in der vorletzten Zeile als Ergebnis der Funktion zurückgegeben. i ist ein Zähler.

Der Grundgedanke ist, i solange zu erhöhen, bis der Rest der Division von n durch i Null ergibt - was bedeutet, dass i Primfaktor von n ist. Wir hängen i in diesem Fall an factors an und starten die Suche für n = n / i und i = 2 erneut. So werden "von unten" alle Primfaktoren gefunden.

Dabei ist aufgrund der imperativen Art besonders auf die Reihenfolge der Anweisungen zu achten!

            (set factors (concat factors (list i)))
            (set n (/ n i))
            (set i 2)

Die ersten beiden Zeilen dürfen untereinander ohne Nebenwirkungen getauscht werden, die letzte muss jedoch immer dort bleiben!

Der Aufruf

*** tScheme, Version 2.7 ***
To quit, type `(quit)` or Ctrl-D (Linux), Ctrl-C (Windows)

-> (load "primfaktoren.s")
function[primfaktoren]
-> (primfaktoren 42)
(2 3 7)
->

© 2006-2019 Solvium.de - Impressum

» Blog powered by Wordpress. Silk icons von FamFamFam.