6.8.11 Übungen
 
Aufgabe 1 Neben dem erweiterten Euklidschen Algorithmus gibt es zur Berechnung des ggT zweier Zahlen noch eine Vorstufe, den (normalen) Euklidschen Algorithmus zur Berechnung des ggT. Er lässt sich am besten rekursiv definieren (das Gleichheitszeichen ist im Sinne der Mathematik zu lesen, ist also kein Zuweisungsoperator):

ggT(a,a) = a
falls a > b dann ggT(a,b) = ggT(b,a-b)
sonst ggT(a,b) = ggT(a,b-a)

Begründen Sie, dass der erweiterte Euklidsche Algorithmus effizienter ist und implementieren Sie diese Methode.
Aufgabe 2 Berechnen Sie mit der in Aufgabe 1 spezifizierten Methode den ggT(8192,2), den ggT(16384,2) und den ggT(32768,2). Da in in allen drei Fällen der erste Parameter eine 2er Potenz ist, erwarten wir als ggT die Zahl 2. Beschreiben Sie Ihre Ergebnisse
 
zu 6.8.11 Lösungen
zur Startseite www.pohlig.de (C) MPohlig 2005