Euklidischer Algorithmus |
| 23.11.2009, 17:50 | estrella28 | Auf diesen Beitrag antworten » |
| Euklidischer Algorithmus 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 |
||
| 23.11.2009, 21:13 | kiste | Auf diesen Beitrag antworten » |
Der Induktionsschritt bei b) ist gerade der Beweis von a).. c) folgt wirklich direkt aus b) weil dann der Bruch eben was ergibt? 
|
||
| 24.11.2009, 09:15 | estrella28 | Auf diesen Beitrag antworten » |
Aber ist a nicht der Induktionsanfang, da das Rekursionstiefe 1 ist, aber ich muss doch im Induktionsschritt tiefer gehen oder??? |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
