Ganzzahlen können verwendet werden, um einzelne Zahlen, aber keine mathematischen Ausdrücke zu speichern. Nehmen wir zum Beispiel an, ich habe den Ausdruck:
6x ^ 2 + 5x + 3
Wie würde ich das Polynom speichern? Ich könnte mein eigenes Objekt erstellen, aber ich sehe nicht, wie ich das Polynom durch Mitgliedsdaten darstellen könnte. Ich möchte keine Funktion zum Auswerten eines übergebenen Arguments erstellen, da ich es nicht nur auswerten muss, sondern auch den Ausdruck manipulieren muss.
Ist ein Vektor meine einzige Option oder gibt es eine geeignetere Lösung?
Eine einfache, aber ineffiziente Art wäre, sie als eine Liste von Koeffizienten zu speichern. Zum Beispiel würde das Polynom in der Frage so aussehen:
%Vor% Wenn ein Begriff fehlt, platzieren Sie eine Null an seiner Stelle. Zum Beispiel würde das Polynom 2x^3 - 4x + 7 wie folgt dargestellt:
Der Grad des Polynoms ergibt sich aus der Länge der Liste minus eins. Diese Darstellung hat einen gravierenden Nachteil: Für spärliche Polynome enthält die Liste viele Nullen.
Eine sinnvollere Darstellung der Termliste eines spärlichen Polynoms ist eine Liste der Terme ungleich Null, wobei jeder Term eine Liste ist, die die Reihenfolge des Terms und den Koeffizienten für diese Ordnung enthält; Der Grad des Polynoms ist durch die Reihenfolge des ersten Terms gegeben. Zum Beispiel würde das Polynom x^100+2x^2+1 durch diese Liste dargestellt:
Als Beispiel dafür, wie nützlich diese Darstellung ist, erstellt das Buch SICP ein einfaches, aber sehr effektives Symbolisches Algebra-System mit der oben beschriebenen zweiten Repräsentation für Polynome .
Eine Liste ist nicht die einzige Option.
Sie können eine Karte (Wörterbuch) verwenden, die den Exponenten dem entsprechenden Koeffizienten zuordnet.
Wenn Sie eine Karte verwenden, wäre Ihr Beispiel
%Vor%Eine Liste von Paaren (Koeffizienten, Exponenten) ist ziemlich Standard. Wenn Sie wissen, dass Ihr Polynom dicht ist, das heißt, alle Exponentenpositionen sind kleine ganze Zahlen im Bereich von 0 bis zu einem kleinen maximalen Exponenten, können Sie das Array verwenden, wie ich gerade Óscar Lopez geschrieben habe. :)
Sie können Ausdrücke als Ausdrucksbäume darstellen. Siehe zum Beispiel .NET Expression Trees .
Dies ermöglicht viel komplexere Ausdrücke als einfache Polynome und diese Ausdrücke können auch mehrere Variablen verwenden.
In .NET können Sie den Ausdrucksbaum als Baum UND Sie können es als Funktion auswerten.
%Vor%Ein objektorientierter Ansatz würde sagen, dass ein Polynom eine Sammlung von Monomen ist und ein Monomum einen Koeffizienten und einen Exponenten zusammenfasst.
Dieser Ansatz funktioniert, wenn Sie ein Polynom wie folgt haben:
%Vor%Ein Ansatz, der eine Datenstruktur an eine polynomische Ordnung bindet, wäre für diesen pathologischen Fall eine furchtbare Verschwendung.
Vektor / Array ist eine offensichtliche Wahl. Abhängig von der Art der Ausdrücke können Sie eine Art von spärlichem Vektortyp betrachten (kundenspezifisch, d. H. Basierend auf einem Wörterbuch oder sogar einer verknüpften Liste, wenn Ihre Ausdrücke 2-3 Koeffizienten ungleich Null 5x ^ 100 + x haben).
In jedem Fall wäre es sinnvoll, über eine benutzerdefinierte Klasse / Schnittstelle zu exponieren, da Sie die Implementierung später ersetzen können. Sie würden wahrscheinlich Standardoperationen (+, -, *, equals) bereitstellen, wenn Sie viel Ausdrucksmanipulationscode schreiben möchten.
Speichern Sie die Koeffizienten einfach in einem Array oder Vektor. Wenn Sie beispielsweise in C ++ nur ganzzahlige Koeffizienten verwenden, können Sie std::vector<int> oder für reelle Zahlen std::vector<double> verwenden. Dann drücken Sie einfach die Koeffizienten in der richtigen Reihenfolge und greifen auf die Variablen mit der Exponentenzahl zu.
Zum Beispiel (wieder in C ++), um 5 * x ^ 3 + 9 * x - 2 zu speichern, könnten Sie folgendes machen:
%Vor%Wenn Sie große, spärliche Polynome haben, dann sollten Sie vielleicht eine Karte anstelle eines Vektors verwenden. Wenn Sie feste Längen haben, verwenden Sie vielleicht ein Array fester Länge statt eines Vektors.
Ich habe C ++ für Beispiele verwendet, aber das gleiche Schema kann in jeder Sprache verwendet werden.
Sie können es auch in umgekehrte polnische Notation umwandeln:
6x ^ 2 + 5x + 3 - & gt; x 2 ^ 6 * x 5 * + 3 +
Wo x und Zahlen auf einen Stapel "geschoben" werden und Operationen (^, *, +) die beiden obersten Werte aus dem Stapel übernehmen und sie durch das Ergebnis der Operation ersetzen. Am Ende erhalten Sie den resultierenden Wert auf dem Stapel.
In dieser Form ist es einfach, beliebig komplexe Ausdrücke zu berechnen.
Diese Darstellung ähnelt auch der Baumdarstellung von Ausdrücken, bei denen Nicht-Blatt-Baumknoten Operationen und Funktionen darstellen und Blattknoten für Konstanten und Variablen.
Was an Bäumen gut ist, ist, dass Sie Ausdrücke auch leicht auswerten können, und Sie können auch Dinge wie eine symbolische Unterscheidung an ihnen vornehmen. Beide haben rekursive Natur.
Tags und Links language-agnostic math variables polynomial-math representation