Algorithmus vereinfachen (Java)

[Benutzername_]

Der Algorithmus soll den Funktionswert der zugehörigen Polynomfunktion an der Stelle x berechnen.

Mir liegt folgender Java Code vor :

Eingabe: Koezienten a[n], a[n-1], ..., a[0], Argument x

q = a [0];
for (i = 1; i <= n; i++) {
          potenz = 1;
for (j = 1; j <= i*i; j++)
          potenz = potenz * x;
          q = a[i] * potenz + q;
}
return q;

Die erste Frage ist :

Wie viele Multiplikationen und Additionen werden - in Abhängigkeit von n - mit
diesem Algorithmus benotigt, um den Wert der Polynomfunktion an einer beliebigen
Stelle x zu berechnen?

Hinweis:
Die Operationen, die von den for-Schleifen benutzt werden, um die Laufvariablen
zu verandern, brauchen nicht berucksichtigt werden.


Die zweite Frage ist :

Wie kann man den Algorithmus verbessern, sodass die Anzahl der Multiplikationen deutlich reduziert werden?

Hinweis: Maximales Ausklammern, Horner-Schema

Ich habe mir schon viel zum Thema im Internet durchgelesen, aber ich finde nichts, dass mir weiterhilft. Ich hoffe Ihr könnt mir bei dieser Aufgabe weiterhelfen.

 

[klauskarambulut]

Frage 1 läßt sich ja recht einfach Beantworten, einfach eine Funktion Multiplikation erstellen.

int counter = 0;
public int multiplikation(int a, int b) {
  counter++;
  return a * b;
}

Nach jedem Durchgang n den wert von counter aufschreiben und zurücksetzen. Und eben multiplikation statt * nutzen.

In der zweiten Schleife gehe ich bei der Bedingung von einem Fehler aus! Es sollte wohl j <= i und nicht j <= i * i sein!

Wie sieht denn eine Typische Polynomfunktin aus?
f(x) = a[3] * x^3 + a[2] * x^2 + a[1] * x^1 + a[0]

in Java
int f(int x) { return a[3] * pow(x, 3) + pow(a[2] * pow(x, 2) + a[1] * pos(x, 1) + a[0]; }

wobei pow mit einer Schleife ziemlich viele Multiplikationen nach sich zieht. Das kann man nur Punktuell verbessern.

Also umschreiben damit das mit den vielen Multiplikationen deutlicher wird.

int f(int x) { return a[3] * x * x * x + pow(a[2] * x * x + a[1] * x + a[0]; }

Und jetzt mal ausklammern.

int f(int x) { return ((a[3] * x + pow(a[2]) * x + a[1]) * x + a[0]; }

Und siehe da wir sind bei 3 Multiplikationen.

int result = 0;
for(i = n; i > 0; i--){ 
  result = result + a[i];
  result = result * x;
}
result += a[0];
return result;

Siehe da nur noch n Multiplikationen

 

[JStein52]

Das war jetzt aber nicht dein Ernst oder ?

int f(int x) { return a[3] * x * x * x + pow(a[2] * x * x + a[1] * x + a[0]; }
Und jetzt mal ausklammern.
int f(int x) { return ((a[3] * x + pow(a[2]) * x + a[1]) * x + a[0]; }

Das sollte wohl so aussehen:

int f(int x) { return (((a[3] * x + a[2]) * x)*x + a[1]) * x + a[0]; }

 

[klauskarambulut]

Um mal auf den Punkt zu kommen, manchmal sieht man das etwas schwer wenn es nur plain text ist. aber
es ist ein "pow(" das ich jeweils übersehen habe. Kann passieren also mal mit Unterstrichen markiert wo es weg muss

int f(int x) { return a[3] * x * x * x + ____a[2] * x * x + a[1] * x + a[0]; }
Und jetzt mal ausklammern.
int f(int x) { return ((a[3] * x + ____a[2]) * x + a[1]) * x + a[0]; }

Obiges hätte zu einem leicht zu entdeckenden Fehler beim kompilieren geführt.

Um dann zur Frage zu kommen
"Das sollte wohl so aussehen:"
Nein sollte es nicht, da hier ein "*x" zuviel vorhanden ist und noch schlimmer, dies auch noch so laufen würde und der Fehler unentdeckt bliebe und potentiell großen Schaden hätte anrichten können.

int f(int x) { return (((a[3] * x + a[2]) * x)__ + a[1]) * x + a[0]; }

Zudem ist auch noch die Klammer obsolet die da in mühevoller Kleinarbeit reingefrickelt wurde.

int f(int x) { return _((a[3] * x + a[2]) * x___ + a[1]) * x + a[0]; }

Aber hauptsache was gesagt, hab dir sogar ewig Zeit gelassen deinen Beitrag entsprechend anzupassen.

 

[JStein52]

Das war nett von dir dass du mir Zeit gelassen hast meinen Fehler zu korrigieren, war aber nur fair. Ich hatte dir schliesslich auch einen Tag Zeit gelassen.
Aber ich hoffe der TO weiss jetzt worum es geht

 

[unigoeftw]

Liebe Grüße von der Uni Göttingen Info 1

Die Aufgabe ist immer noch verwirrend gestellt. mfg^^