+2 Daumen
154 Aufrufe

Algorithmus „Hornerschema“

1. Setze k ← n − 1 und z ← an. 

2. Falls k < 0 gehe zu Schritt 6.

3. Setze z ← z · x0 + ak. 

4. Setze k ← k − 1. 

5. Gehe zu Schritt 2. 

6. Gib z aus. 

a) Beweisen Sie die partielle Korrektheit dieses Algorithmus für alle n ≥ 0. Hinweis: Verwenden Sie vollständige Induktion bezüglich n. 

b) Zeigen Sie, dass der Algorithmus terminiert. 

c) Vergleichen Sie die beiden Algorithmen zur Auswertung von p bezüglich der Anzahl der benötigten Multiplikationen!

Gefragt von

Bearbeite deine Aufgaben bitte eigenständig.

Gruß Ohlebusch

1 Antwort

0 Daumen

Wenn n=0 dann k=-1, also k<0. Also gehen wir zum 6ten Schritt  und geben z aus, das vom ersten Schritt gleich a_0 ist.


Was müsste der Algorithmus für k=0 ausgeben? Ist das Ergebnis richtig?



 

Beantwortet von 1,5 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...