Euklidischer Algorithmus

Neue Frage »

Auf diesen Beitrag antworten »
Gast Euklidischer Algorithmus

Hallo

Ich habe folgende Aufgabe:

Betrachten Sie die rekursive Variante des Euklidischen Algorithmus. Sei
[latex] m \geq n [/latex].

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]

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
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »