Rekursive Darstellung des Horner Schema?
Wie der Fragetitel schon sagt, muss ich das Horner Schema rekursiv darstellen (in beliebiger Programmiersprache).
Ich hab einige Stunden damit verbracht, aber bin auf keine rekursive Lösung gekommen, die für Polynome mit Grad >= 3 funktioniert.
Anzumerken ist auch, dass nach einer Multiplikation kein rekursiver Abstieg erfolgen darf und aufgrund der Def. des Horner Schema darf auch nicht mit Potenzen gearbeitet werden.
Die Lösung muss rein auf rekursivem Auf-/Abstieg basieren.
Zu meinen Ansätzen:
Je nach dem, wie ich versucht habe das Schema rekursiv darzustellen, wurde entweder das x nicht richtig ausgeklammert, sodass das Anfangspolynom nicht richtig dargestellt wurde, oder die Anordnung der Koeffizienten war falsch, weshalb das Ergebnis dementsprechend falsch wurde.
Ich hoffe, dass mir hier geholfen werden kann!
Danke für eure Mühen vorab
Sortieren ist verboten
Indexberechnung nur über Post/Prefix
Danke an alle, die sich die Mühe gemacht haben!
Lösung in Java:
public static long horner(long x, long[] a, int i) {
if (a == null || a.length == 0) return 0;
if (i == a.length) return horner(x, a, 0);
if (++i == a.length) return a[--i];
--i;
return a[i] + horner(x, a, ++i) * x;
}
1 Antwort
Dein Ansatz:
public static long horner(long x, long[] a, int i) {
if (a == null || a.length == 0) return 0;
if (i == 0) return a[0];
Soweit ok (wennauch etwas redundant).
return (horner(x, a, --i) + a[i]) * x;
}
Das sieht komisch aus, denn das Ergebnis ist z.B. bei x==0 immer 0, wenn das Polynom nicht Grad 0 hat.
Ich nehme mal an, dass a[i] der Koeffizient von xⁱ ist. Dann sollte es so gehen:
return a[i] + horner(x, a, --i) * x;
}
Das dröselt sich auf zu a[i] + (a[i–1] + (a[i–2] + ( ... + a[0]*x )*x )*x )*x
Ich nehme mal an, dass a[i] der Koeffizient von xⁱ ist
Wenn die Annahme falsch ist, musst Du eben überall a[k] durch a[a.length–1–k] ersetzen:
public static long horner(long x, long[] a, int i) {
if (a == null || a.length == 0) return 0;
if (i == 0) return a[a.length-1];
return a[a.length-1-i] + horner(x, a, --i) * x;
}
Beachte, dass die innerste Rekursion dann das letzte Element aus a verwendet.
Der allererste Rekursionsschritt verbrät a[a.length–i–1]==a[0].
Anders als bei meiner angenommenen Sortierung muss hier die Länge von a genau der Grad+1 sein. Ist a länger, werden die ersten Elemente von a ignoriert.
Aber dann wäre es einfacher (und verständlicher), wenn Du die Rekursion mit i=0 startest und bei i=a.length–1 abbrichst:
public static long horner(long x, long[] a, int i) {
if (a == null || a.length == 0) return 0;
if (i == a.length-1) return a[i];
return a[i] + horner(x, a, i+1) * x;
}
Wird wohl stimmen und danke für die Mühe,
ich hab allerdings oben vergessen zu erwähnen ( steht irgendwo in den Kommentaren unter dem anderen Beitrag ), dass Sortieren verboten ist und Indexberechnung nur über Post/Prefix gestattet ist, da sonst die Testklasse fehler meldet
Sortieren verboten
Wie kommst Du auf sortieren?
Indexberechnung nur über Post/Prefix
Jetzt wird's interessant! Aber klären wir erst mal, was denn in a drin steht:
Ich nehme mal an, dass a[i] der Koeffizient von xⁱ ist
Sorry, da hatte ich einen Knoten im Hirn! Wegen „return a[0];“ habe ich vermutet, dass a[0] bei Dir der höchste Koeffizient ist. Meine Annahme sagt aber genau das Gegenteil (weil es praktischer und verständlicher ist, wenn a[0] das konstante Glied ist). Das habe ich durcheinander gebracht.
Also nochmal:
- Falls a[0] der höchste Koeffizient ist, passt meine Antwort, und Dein Einwand „es soll a[0] + ( a[1] + ... sein“ ist daneben.
- Falls a[0] das konstante Glied ist, ist Dein Einwand gerechtfertigt, und die Version in meinem Kommentar stimmt. Ob Du dort i+1 oder ++i schreibst, ist doch egal.
Also, nochmal Entschulding, ich hatte wohl einen Tunnelblick, für mich war alles gleich ^^
Bin tatsächlich auch auf die Lösung gekommen durch die Umordnung der Glieder, wäre instinktiv auch mein Ansatz gewesen, aber wie gesagt, Tunnelblick
Meine Lösung:
public static long horner(long x, long[] a, int i) {
if (a == null || a.length == 0) return 0;
if (i == a.length) return horner(x, a, 0);
if (++i == a.length) return a[--i];
--i;
return a[i] + horner(x, a, ++i) * x;
}
Scheint zu passen (obwohl die zweite Zeile seltsam ausschaut).
if (a == null || a.length == 0) return 0;
Klar: ein leeres Array ist ein Polynom p(x)=0 mit Grad –1. Das ist immer 0. Dieser Fall kann nur im ersten Aufruf eintreten.
if (i == a.length) return horner(x, a, 0);
Das sieht nach einer Endlosrekursion aus, aber der Fall a.length==0 ist ja schon oben abgefangen. Auch dieser Fall kann nur im ersten Aufruf eintreten, wenn jemand (böswillig?) einen „falschen“ Wert für i übergibt. Die „falschen“ Werte i>a.length werden aber nicht abgefangen. Das ist inkonsistent.
if (++i == a.length) return a[--i];
Das beendet die Rekursion bei i==a.length–1, also effektiv bei Grad 0. Kann man machen, aber wenn Du den Fall „leeres Array“ oben vereinfachst, ist es nicht nötig. Lass die Rekursion noch einen Schritt weiter laufen und beende erst bei Grad –1 (mit return 0).
Dumm wäre es, wenn die Aufgabenstellung verlangt, dass der initiale Aufruf mit i==a.length erfolgt. Dann sind Deine umständlichen Abfragen wohl alle so und in dieser Reihenfolge nötig. Allerdings solltest Du das ausführlich kommentieren, sonst hält man Dich für doof :-)
Wenn der initiale Aufruf mit i==0 beginnen darf, geht es also auch so:
/**
* Calculates a given polynomial function of degree
* a.length-1-i using horner's method
* a[i+k] represents the corresponding coefficient for xᵏ
*
* @param x Value of x
* @param a Array with coefficients (a[0]..a[i-1] is ignored)
* @param i index of first coefficient (for x⁰).
* @return Polynomial function value (== Σₖ a[i+k]·xᵏ)
*/
public static long horner(long x, long[] a, int i) {
if (a == null || i>=a.length) // degree <= -1
return 0;
return a[i] + horner(x, a, ++i) * x; // degree >= 0
}
Dass i und ++i in einem Ausdruck vorkommt, funktioniert zwar in Java, ist aber grundsätzlich extrem fehleranfällig. Ich verstehe ehrlich gesagt nicht, warum „a[i]+horner()“ erlaubt sein soll, aber i+1 nicht. Und noch weniger, wie ein Testprogramm dies prüfen will. Wenn da ein stures grep über den Quelltext läuft, musst Du wahrscheinlich auch die Kommentare anpassen.
Verstehe ehrlich gesagt nicht einmal den Sinn hinter dieser Aufgabe - Modul befasst sich eben mit Algorithmen und Datenstrukturen
Ob der Code nun verständlich ist oder nicht, spielt auch keine Rolle (zumindest hier), da wir die Klassen abgeben müssen und diese automatisch bewertet werden, ohne dass der Professor sie je sieht
Normalerweise würde ich auch jegliche Randfälle behandeln oder fehlerhafte Eingaben, aber der Test wurde explizit so beschrieben, dass z.B. beim ersten Aufruf von horner(..) i immer gleich a.length sei
Und zu dem Punkt wie die Addition etc. überprüft werden soll: Für alles andere als Indexberechnung müssen wir Hilfsmethoden einer seperaten Klasse aufrufen, die [*,+,_,\] berechnen
Hab ich wohl vergessen zu erwähnen, verständnishalber empfand ich das aber besser :)
Übrigens zu dem Ansatz:
"Lass die Rekursion noch einen Schritt weiterlaufen und beende erst bei Grad -1"
Macht wohl durchaus Sinn, um die eine Fallunterscheidung nicht explizit auszudrücken, allerdings meckert dann die Testklasse, dass die Rekursionstiefe nicht richtig ist, im Sinne von: Der vorgegebene Algorithmus wurde nicht richtig implementiert, auch wenn es wohl funktioniert
beim ersten Aufruf von horner(..) i immer gleich a.length
Autsch! Das ist nur sinnvoll, wenn a[0] der höchste Koeffizient ist. Die Rekursion verrechnet ja den konstanten Koeffizienten mit dem Restpolynom a[ 0 ... ––i ]. Der Parameter i gibt dann die effektive Restlänge von a an.
Wenn a[0] aber das konstante Glied ist, wird es abgebissen und die Rekursion läuft über die hinteren Koeffizienten a[ ++i ... Grad ] weiter. Java bietet keine Möglichkeit für solche Teilarrays. Man muss sich also mit a und dem Startindex i behelfen. Aber dann ist es nur logisch, wenn die Rekursion mit Startindex i==0 beginnt.
Die Kombination „Start mit i==a.length“ und „a[0]==konstantes Glied“ ist so krank, dass Du unbedingt nochmal nachschauen solltest, ob das tatsächlich so gegeben ist.
Wenn aber schon eine effiziente Implementierung fehlschägt, weil sie nicht die „richtige“ Tiefe hat, halte ich alles für möglich. Vielleicht will der Prof euch nur zeigen, wie man ein perfektes Java-Programm schreibt: umständlich, undurchschaubar, fehleranfällig und ineffizient.
Ein professioneller Java-Programmierer braucht für die Rechnung 1+1 etwa 250 Zeilen Code und 3 Fremdbibliotheken. Das Ergebnis erscheint dann nach wenigen Minuten − falls das Programm nicht vorher mit „out of memory“ abbricht :-(
Wie gesagt, die Aufgabe und Bedingungen dafür sind etwas komisch
Normalerweise gibt es so viele (sinnlose) Einschränkungen nicht und man ist relativ frei, wie man die Problemstellung lösen darf :)
Danke für deine Einwände und Erklärungen
Gern geschehen. Wenn's läuft, ist ja alles gut. Lies meine Kommentare einfach als „Nein, es liegt nicht an Dir!“ :-)
Danke für den Ansatz, allerdings ist das Polynom hier schlicht falsch dargestellt.
Es sollte eben die Form a[0] + ( a[1] + ... (a[i] * x ) * x ) * ... * x annehmen, damit jeder Koeffizient korrekt verrechnet wird
Das ist ja genau das Schema 🤔