SOLVIUM

Programmierung

ggT berechnen in tScheme

Der Code

Der Code zum Berechnen des ggT besteht aus einer einzigen rekursiven Funktion:

(define (ggt m n)
   (if (= m n) m
       (< m n) (ggt m (- n m))
               (ggt n (- m n))
   )
)

Die Funktionsweise

Der Algorithmus zur Berechnung des größten gemeinsamen Teilers ist folgender: Sind m und n gleich, haben wir den ggT gefunden. Andernfalls berechnen wir den ggT von der kleineren Zahl und der Differenz beider Zahlen.

Dieses Vorgehen lässt sich leichter an einem Zahlenbeispiel verdeutlichen.
Sei m=11 und n=44, ist klar, dass der größte gemeinsame Teiler 11 ist. Dies folgt auch aus dem oben gegebenen Algorithums.
Zunächst wird
(ggt 11 44) aufgerufen. Da m ungleich n, erfolgt der Aufruf
(ggt 11 33) - da hier ebenfalls m ungleich n,
(ggt 11 22)
(ggt 11 11) - nun ist m = n, es wird das Resultat m = 11 zurückgegeben.

Die Berechnung des ggT wird bei der Berechnung des kgV verwendet!

Der Aufruf

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

-> (load "ggt.s")
function[ggt]
-> (ggt 11 44)
11
->

© 2006-2019 Solvium.de - Impressum

» Blog powered by Wordpress. Silk icons von FamFamFam.