Gast unregistriert
|
|
Hallo
Ich habe folgende Aufgabe:
Betrachten Sie die rekursive Variante des Euklidischen Algorithmus. Sei
.
a) Beweisen Sie, dass für den Rest r der Division von m durch n gilt:
r< (m/2)
b) Beweisen sie, dass in Rekursionstiefe 1+2k für den aktuellen Rest r und das ursprüngliche m gilt:
c) Zeigen Sie mit dem Wissen aus a und b, dass die maximale Tiefe des rekursiven Euklidischen Algorithmus höchstens 1+2 * log(basis2)(m) beträgt.
a habe ich hinbekommen, bei b würde ich eine induktion über k machen, nur weiß ich nicht wie der induktionsschritt funktionieren soll.
zu c, da weiß ich auch leider überhaupt nicht wie ich das beweisen soll.
LG
estrella28
|
|
24.11.2009 09:05 |
|
|