Effiziente rechnung mit potenz < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Geben Sie die Abfolge von Additionen und Multiplikatinen an, um [mm] y(x+1)^{19} [/mm] möglichst effizient zu berechnen . Verwenden Sie die Variablen a,b,... für Zwischenergebnisse. WieivleMultiplikationen werden benötigt. |
Ich habe mir das so überlegt:
Als erstes wird die Klammer ausgerechnet.
x+1 = a und dann a 19mal mit einander multipliziert.
Doch das scheint mir viel zu einfach. Kann jemand sagen ob das so richtig ist oder nicht.
Vielen Dank Elisa
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:10 So 31.10.2010 | | Autor: | felixf |
Moin!
> Geben Sie die Abfolge von Additionen und Multiplikatinen
> an, um [mm]y(x+1)^{19}[/mm] möglichst effizient zu berechnen .
> Verwenden Sie die Variablen a,b,... für
> Zwischenergebnisse. WieivleMultiplikationen werden
> benötigt.
> Ich habe mir das so überlegt:
> Als erstes wird die Klammer ausgerechnet.
> x+1 = a und dann a 19mal mit einander multipliziert.
Du meist 18 mal.
> Doch das scheint mir viel zu einfach. Kann jemand sagen ob
> das so richtig ist oder nicht.
Das ist nicht optimal.
Um etwa [mm] $a^4$ [/mm] auszurechnen, kannst du $b = a * a$, $c = b * a$, $d = c * a$ ausrechnen (drei Multiplikationen) oder $b = a * a$, $c = b * b$ ausrechnen (zwei Multiplikationen).
Etwas aehnliches kannst du hier auch machen. Beachte, dass $19 = [mm] 2^4 [/mm] + 2 + 1$ ist
LG Felix
|
|
|
|
