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)) ) )
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!
*** 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-2021 Solvium.de - Impressum