Dr. Kai-Friederike Oelbermann Wintersemester 2015/16Dipl.-Math. Alina Bondarava OVGU Magdeburg
Ubungen zur Algorithmischen Mathematik
Blatt 6
1. Seien a0 := 1, a1 := 1 und fur k 2 : ak := ak1 + ak2 die Fibonaccizahlen aus Aufgabe 3,Blatt 5.
(a) Zeigen Sie, dass der Euklidische Algorithmus bei Eingabe von a = ak+2, b = ak+1, k 2 N0,genau k + 1 Divisionen ausfuhrt.
(b) Zeigen Sie per vollstandiger Induktion fur k 2 N0
ak =1p5
0
@ 1 +
p5
2
!k+1 1
p5
2
!k+11
A.
2. (F5 PunkteF)
(a) Schreiben Sie ein Programm, welches Ihnen die Anzahl der benotigten Divisionen sowie dieAnzahl der Divisionen mit qi = 1 bzw. qi = 2 im Euklidischen Algorithmus zururck gibt. qibezeichnet (wie in der Vorlesung) den ganzzahligen Quotienten bei der Division mit Rest inden Iterationsschritten des Euklidischen Algorithmus.
(b) Schreiben Sie nun ein Programm, welches den Euklidischen Algorithmus automatisch aufZahlenpaare (a, b) mit a, b 2 N und a, b M anwendet. Der Maximalwert M soll vom Be-nutzer eingegeben werden konnen. Das Programm soll auch den Prozentsatz der Divisionenmit qi = 1 bzw. qi = 2 berechnen und die maximale Anzahl an benotigten Divisionen aus-geben, die wahrend der Berechnungen bei einem Durchgang des Euklidischen Algorithmusauftritt.
(c) Schreiben Sie ein Programm, welches experimentell die relative Haufigkeit fur die Ereignisse:ggT (a, b) = 1 bzw. ggT (a, b) 10 feststellt. Wahlen Sie dafur a, b 2 N und a, b M . DerMaximalwert M soll wieder vom Benutzer eingegeben werden konnen.
3. (F5 PunkteF) Zu Zahlen a0, a1, . . . , an 2 Z mit ai 1, i 1, ist der zugehorige regulareKettenbruch die rationale Zahl
[a0; a1, . . . , an] = a0 +1
a1 +1
a2+1
...+ 1an1+ 1an
(a) Sei x 2 Q. Zeigen Sie: Es existieren a0, a1, . . . , an 2 Z mit ai 1, i 1, so dass x =[a0; a1, . . . , an].Hinweis. Euklidischer Algorithmus mit den Eingabewerten a und b, wobei x = a/b, mita 2 Z, b 2 N
(b) Schreiben Sie ein Programm, welches zu einer gegebenen nichtnegativen rationalen Zahl dieKettenbruchdarstellung in der Form [a0; a1, . . . , an] berechnet. Die nichtnegative rationaleZahl a soll als Zahlenpaar (a, b), a 2 N0, b 2 N, eingegebenen werden.
(c) (F5 PunkteF) Schreiben Sie ein Programm, welches zu einem Kettenbruch [a0; a1, . . . , an]mit a0 0 die entsprechende rationale Zahl in gekurzter Darstellung ausgibt. Es durfen hiernur integer-Variablen benutzt werden.
1
