7.4.6 Ü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
 
Aufgabe 3 Erstellen Sie ein ein Diagramm für die benötigte Zeit in Abhängigkeit von n im rekursiven Algorithmus für die Berechnung von Fibonacci-Zahlen. Verwenden Sie FibonacciDemo.java.
 
Aufgabe 4 Implementieren Sie in dem Programm FibinacciDemo2.java eine Uhr.  Vergleichen Sie den Aufwand zur Berechung von Fibonacci-Zahlen in der nichtrekursiven Methode mit dem in der rekursiven Methode.
 
Aufgabe 5 Fibonnaci-Zahlen lassen sich auch explizit berechnen; denn es gilt:

(Kann jemand die Formel beweisen? Zusendung erwünscht)
Implementieren Sie eine Methode fibonacci(int n): long die die obige Formel zur Berechnung verwendet, und integrieren Sie diese Formel in ein Programm FibionacciDemo3.java. Auch hier bauen Sie eine Uhr ein, um die Effizienz dieses Programms zu testen. Vergleichen Sie die Ergebnisse mit den bisherigen Algorithmen. Welche Methode übernehmen Sie in Mathematik. java?

Anmerkung: Um die Methoden zu finden, mit denen man Wurzeln und Potenzen berechnen kann, schlagen Sie in der Javadokumentation der Klasse Math nach. (Bei Java Editor bei Hilfe - API).
 
   
zu 7.4.6 Lösungen
zu 8. GUI und API für die Klasse Mathematik
8.1 GUI und Ereignisbehandlung
8.1.1 Eine JFrame-Vorlage step bei step
zur Startseite www.pohlig.de (C) MPohlig 2006