Gast
unregistriert
 |
|
Hallo
Ich habe folgende Aufgabe:
Betrachten Sie die rekursive Variante des Euklidischen Algorithmus. Sei
![[latex] m \geq n [/latex]](http://www.matheboard.de/latex2png/latex2png.php? m \geq n ) .
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:
![[latex] r < \frac{m}{2^{k+1}} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? r < \frac{m}{2^{k+1}} )
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 |
|
|
