Euklidischer Algorithmus |
24.11.2009, 09:05 | Auf diesen Beitrag antworten » |
Gast | Euklidischer Algorithmus 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 |
|
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|