Polynome

1. Aufgabe

Gegenstand dieser Aufgabe sind Polynomfunktionen, kurz auch Polynome genannt. Formal ist ein Polynom als eine Summe von Vielfachen von Potenzen einer Variablen x definiert:

Pn(x) = anxn + an-1xn-1 + ... + a2x2 + a1x + a0.

Die Variable x wie auch die Koeffizienten ai können beliebige reelle Werte annehmen, wir sprechen von einem reellen Polynom. Als Grad des Polynoms wird der höchste Exponent n bezeichnet, für den der Koeffizient an des Ausdrucks anxn nicht null ist. Dieser Koeffizient wird auch Leitkoeffizient genannt.

Entwickeln Sie eine Klasse Polynom, die – möglichst einfallsreich – die unterschiedlichen Konstrukte (Eigenschaften, Methoden, Indexer, Operatoren usw.) zur Definition einer Klasse in C# in Anspruch nimmt. Die Dienstleistungen der Klasse Polynom werden in Tabelle 1 genauer spezifiziert:

Element

Beschreibung

Konstruktor

public Polynom ();

Der Standardkonstruktor erzeugt ein Nullpolynom. Dieses besitzt den Rang Null, der Leitkoeffizient hat ebenfalls den Wert Null.

Konstruktor

public Polynom (double[] values);

Dieser Konstruktor legt ein Polynom mit den Koeffizienten des Arrays values an. Der Grad des Polynoms ist logischerweise values.Length - 1.

Eigenschaft Rank

public int Rank { get; }

Liefert den Grad des Polynoms zurück.

Eigenschaft IsZero

public bool IsZero { get; }

Liefert true zurück, wenn das aktuelle Polynom das Nullpolynom ist, andernfalls false.

Operator + bzw. -

public static Polynom operator+ (Polynom p1, Polynom p2);
public static Polynom operator- (Polynom p1, Polynom p2);

Die Addition (Subtraktion) eines Polynoms des Grades n mit (von) einem Polynom des Grades m ergibt ein Polynom des Grades kleiner-gleich Max(n, m). Die Koeffizienten des Ergebnispolynoms werden jeweils durch Addition (Subtraktion) der gleichnamigen Koeffizienten (das sind die Koeffizienten mit der gleichen Potenz von x) der zwei beteiligten Polynome gebildet.

Operator *

public static Polynom operator* (Polynom p1, Polynom p2);

Die Polynommultiplikation eines Polynoms des Grades n mit einem Polynom des Grades m ergibt ein Polynom des Grades n + m. Bei der Polynommultiplikation multiplizieren Sie jedes aixi des einen Polynoms mit allen bjxj des anderen Polynoms und summieren die Koeffizienten der jeweilig passenden Grade.

Operator /

public static Polynom operator/ (Polynom p1, Polynom p2);

Die Division (mit Rest) von zwei Polynomen besagt, dass es zu zwei Polynomen p1 und p2 immer zwei weitere Polynome q und r gibt, so dass p1 = q * p2 + r gilt. Algorithmisch betrachtet funktioniert die Polynomdivision im Grunde sehr ähnlich wie die Division von ganzen Zahlen: Man zieht vom Dividenden passende Vielfache des Divisors solange ab, bis kein Rest bleibt oder das Restpolynom einen kleineren Polynomgrad als das Divisorpolynom besitzt.

Operator %

public static Polynom operator% (Polynom p1, Polynom p2);

Der %-Operator ist das Gegenstück zum /-Operator: Bleibt bei der Polynomdivision ein Restpolynom übrig (Polynomgrad muss kleiner als der des Divisors sein), wird dieses vom %-Operator zurückgeliefert. Andernfalls wird das Nullpolynom zurückgegeben.

Methode Clone

public Object Clone ();

Erstellt eine Polynomkopie auf Basis der tiefen Kopierstrategie (Schnittstelle ICloneable).

Methode CompareTo

public int CompareTo (Polynom p);

Der Vergleich zweier Polynome (auf Basis der Schnittstelle IComparable<Polynom>) ist wie folgt definiert: Ein Polynom ist größer als ein anderes, wenn sein Grad größer ist. Ist der Grad gleich, sind der Reihe nach alle Koeffizienten, beginnend bei an, zu vergleichen. Sind alle Koeffizienten gleich, sind die Polynome gleich.

Indexer

public double this [double x] { get; }

Wertet das Polynom an der Stelle x aus. Dabei soll, um unnötige Berechnungen von Potenzen einzusparen, der Wert mit dem sogenannten Horner-Schema berechnet werden. Die Arbeitsweise des Horner-Schemas kann man leicht erkennen, wenn wir für die Polynome bis zum dritten Grad exemplarisch folgende Umformungen vornehmen:

P0(x) = a0,

P1(x) = a1x + a0,

P2(x) = a2x2 + a1x + a0 = (a2x + a1)x + a0,

P3(x) = a3x3 + a2x2 + a1x + a0 = ((a3x + a2)x + a1)x + a0.

Jetzt wird die Wiederholstruktur des Horner-Schemas deutlich erkennbar:

y3 = a3.

y2 = a2 + x * y3.

y1 = a1 + x * y2.

y0 = a0 + x * y1.

Der gesuchte Polynomwert entspricht nun dem Wert y0.

Operator == bzw. !=

public static bool operator== (Polynom p1, Polynom p2);
public static bool operator!= (Polynom p1, Polynom p2);

Test auf Gleichheit bzw. Ungleichheit zweier Polynome.

Operator <, <=, > bzw. >=

public static bool operator<  (Polynom p1, Polynom p2);
public static bool operator<= (Polynom p1, Polynom p2);
public static bool operator>  (Polynom p1, Polynom p2);
public static bool operator>= (Polynom p1, Polynom p2);

Umsetzung der mathematischen Relationen kleiner, kleiner-gleich, größer und größer-gleich für zwei Polynome p1 und p2, siehe dazu auch die Beschreibung der CompareTo-Methode.

Methode ToString

public override String ToString();

Stellt das aktuelle Polynom in einer Zeichenkette dar. Diese sollte beispielsweise die Form

3x^3 + 0x^2 - 4x^1 + 2

haben oder noch besser

3x^3 - 4x^1 + 2

Tabelle 1. Elemente der Klasse Polynom.


Zur Überprüfung Ihrer Implementierung folgen einige Beispiele. Für die beiden Polynome

P(x) = 3x3 - 4x + 2

und

Q(x) = 5x2 + 3x + 3

lautet die Summe

P(x) + Q(x) = 3x3 + 5x2 - x + 5. Die Differenz ergibt sich zu

P(x) - Q(x) = 3x3 - 5x2 - 7x - 1.

Das Produkt der Polynome lautet

P(x) * Q(x) = 15x5 + 9x4 - 11x3 - 2x2 - 6x + 6.

Auf die Division gehen wir etwas ausführlicher ein. Wir teilen das Polynom x3 + 6x2 + 3x - 10 durch das Polynom x + 5. Zuerst müssen wir bestimmen, wie oft x + 5 in das erste Polynom hineinpasst. Man betrachtet dabei stets die höchste Potenz aus beiden Polynomen (also x3 aus dem ersten und x aus dem zweiten Polynom) und berechnet, wie oft x in x3 hineinpasst. Anders herum formuliert: Mit was muss man x malnehmen, so dass x3 herauskommt? Natürlich mit x2, das erste Teilresultat der Division ergibt sich nun zu

(x3 + 6x2 + 3x - 10) : (x + 5) = x2

Wie bei der Division von ganzen Zahlen multipliziert man jetzt den neuen Bestandteil des Ergebnisses mit dem Divisor und schreibt ihn passend unter den Dividenden, also gleiche Potenzen von x sind jeweils untereinander zu schreiben:

(x3 + 6x2 + 3x - 10) : (x + 5) = x2

 x3 + 5x2

Nun wird die Subtraktion durchgeführt und werden anschließend alle restlichen Glieder des Polynoms heruntergeholt:

Der Rest hat nur noch den Polynomgrad 2, wir haben also das Problem schon um einen Grad verringert. Nun stehen wir wieder vor der Ausgangsfrage: Wie oft passt das x aus dem Divisor in das x2, die höchste Potenz des Restes. Offensichtlich x-Mal, damit ist der nächste Summand des Quotienten (des Ergebnisses) +x:

Die jetzt noch zu beantwortende Frage lautet Wie oft passt x in -2x?. Offensichtlich -2-Mal, und die (letzte) Subtraktion sieht nun so aus:

Dass diese Polynomdivision keinen Rest besitzt, ist in der Tat Zufall – oder um es doch ehrlich zu sagen: Ich habe es mit Absicht so hingedeichselt :-). Es kann allerdings auch der Fall vorliegen, dass das Restpolynom nicht mehr durch das Divisorpolynom teilbar ist. In diesem Fall weist die Polynomdivision einen Rest auf. Neben der Division gibt es daher auch die Modulo-Operation für Polynome, also die Bestimmung des Restpolynoms bei Polynomdivision, siehe dazu folgendes Beispiel:

2. Lösung

Für die Ablage der Koeffizienten in einem Polynom-Objekt gibt es mehrere Möglichkeiten. Mit einer generischen Klasse des Typs List<double> vereinfacht sich die Implementierung der einzelnen Polynomfunktionen erheblich. Auch Arrays wären eine Alternative. Da ihre Länge fix ist, vergrößert sich jedoch der Aufwand beim Anlegen neuer Arrays mit veränderter Länge. Das Grundgerüst der Klasse (Instanzvariablen, Konstruktoren und Eigenschaften) finden Sie in Listing 1 vor. Auf die Methode Horner, deren Aufruf Sie im Indexer der Klasse vorfinden, kommen wir bei den Hilfsmethoden der Klasse zu sprechen:

01: class Polynom : ICloneable, IComparable<Polynom>
02: {
03:     private List<double> coefficients;
04: 
05:     // c'tors
06:     public Polynom()
07:     {
08:         // create zero polynom
09:         this.coefficients = new List<double>();
10:         this.coefficients.Add(0.0);
11:     }
12: 
13:     public Polynom(double[] coefficients)
14:     {
15:         // remove leading zeros
16:         int max = coefficients.Length - 1;
17:         while (max > 0 && coefficients[max] == 0)
18:             max--;
19: 
20:         // create list with specified coefficients
21:         this.coefficients = new List<double>();
22:         for (int i = 0; i <= max; i++)
23:             this.coefficients.Add(coefficients[i]);
24:     }
25: 
26:     public Polynom(List<double> coefficients)
27:     {
28:         this.coefficients = new List<double>();
29:         this.coefficients.AddRange(coefficients);
30:         this.RemoveLeadingZeros();
31:     }
32: 
33:     // properties
34:     public int Rank
35:     {
36:         get
37:         {
38:             return this.coefficients.Count - 1;
39:         }
40:     }
41: 
42:     public bool IsZero
43:     {
44:         get
45:         {
46:             return this.coefficients.Count == 1 && this.coefficients[0] == 0;
47:         }
48:     }
49: 
50:     // compute value - using indexer
51:     public double this[double x]
52:     {
53:         get
54:         {
55:             return this.Horner(x);
56:         }
57:     }
58:     ....
59: }

Beispiel 1. Klasse Polynom: Konstruktoren, Eigenschaften und Indexer.


Feinheiten der Implementierung sind beispielsweise das Entfernen führender Nullen eines Polynoms, die beim Addieren oder Subtrahieren entstehen können. Um den Aufruf von RemoveLeadingZeros nicht in der gesamten Implementierung verstreuen zu müssen, ist er in Zeile 30 von Listing 1 an einer zentralen Stelle (Konstruktor) platziert.

Es folgt die Implementierung der arithmetischen Operatoren in Listing 2. Das Subtrahieren zweier Polynome wird sinnigerweise auf die Addition zurückgeführt. Dabei kommt die unäre Multiplikation mit der Konstanten -1.0 zum Einsatz:

001: // unary operators + and -
002: public static Polynom operator+ (Polynom p)
003: {
004:     return (Polynom) p.Clone();
005: }
006: 
007: public static Polynom operator- (Polynom p)
008: {
009:     Polynom tmp = (Polynom) p.Clone();
010:     for (int i = 0; i < tmp.coefficients.Count; i++)
011:         tmp.coefficients[i] *= -1.0;
012:     return tmp;
013: }
014: 
015: // binary operators +, -, *, / and %
016: public static Polynom operator+ (Polynom p1, Polynom p2)
017: {
018:     List<double> tmp = new List<double>();
019: 
020:     // add common cofficients
021:     int minRank = Math.Min(p1.Rank, p2.Rank);
022:     for (int i = 0; i <= minRank; i++)
023:         tmp.Add(p1.coefficients[i] + p2.coefficients[i]);
024: 
025:     // add remaining cofficients (just one polynom is concerned)
026:     for (int i = minRank + 1; i < p1.coefficients.Count; i++)
027:         tmp.Add(p1.coefficients[i]);
028:     for (int i = minRank + 1; i < p2.coefficients.Count; i++)
029:         tmp.Add(p2.coefficients[i]);
030: 
031:     Polynom p = new Polynom(tmp);
032:     return p;
033: }
034: 
035: public static Polynom operator- (Polynom p1, Polynom p2)
036: {
037:     Polynom tmp = -p2;
038:     tmp = p1 + tmp;
039:     return tmp;
040: }
041: 
042: public static Polynom operator* (Polynom p1, Polynom p2)
043: {
044:     double[] tmp = new double[p1.Rank + p2.Rank + 1];
045: 
046:     for (int i = 0; i <= p1.Rank; i ++)
047:         for (int j = 0; j <= p2.Rank; j ++)
048:             tmp[i + j] +=
049:                 p1.coefficients[i] * p2.coefficients[j];
050: 
051:     return new Polynom(tmp);
052: }
053: 
054: public static Polynom operator/ (Polynom p1, Polynom p2)
055: {
056:     if (p1.Rank < p2.Rank)    // degree of numerator polynom is less than
057:         return new Polynom(); // degree of denominator polynom
058: 
059:     // need copies of arguments
060:     Polynom tmp1 = (Polynom) p1.Clone();
061:     Polynom tmp2 = (Polynom) p2.Clone();
062: 
063:     // create coefficients array with zero coefficients
064:     double[] rescoeff = new double[p1.Rank - p2.Rank + 1];
065: 
066:     // apply algorithm of polynom division
067:     for (int i = rescoeff.Length - 1; i >= 0 ; i--)
068:     {
069:         // premature end of division reached (comparing degrees)
070:         if (tmp1.Rank < p2.Rank)
071:             break;
072: 
073:         // calculate next coefficient of result polynom
074:         double coeff =
075:             tmp1.coefficients[tmp1.coefficients.Count - 1] /
076:             tmp2.coefficients[tmp2.coefficients.Count - 1];
077: 
078:         // multiply denominator polynom with coefficient
079:         tmp2 = tmp2 * coeff;
080: 
081:         // calculate difference of ranks
082:         int diffRank = tmp1.Rank - p2.Rank;
083: 
084:         // multiply denominator polynom with one ore more 'x'
085:         Polynom px = new Polynom(new double[] { 0, 1 });
086:         for (int j = 0; j < diffRank; j++)
087:             tmp2 = tmp2 * px;
088: 
089:         // subtract denominator polynom from numerator polynom
090:         tmp1 = tmp1 - tmp2;
091: 
092:         // poke calculated coefficient into result polynom
093:         rescoeff[diffRank] = coeff;
094: 
095:         // restore denominator polynom
096:         tmp2 = (Polynom) p2.Clone();
097:     }
098: 
099:     return new Polynom(rescoeff);
100: }
101: 
102: public static Polynom operator% (Polynom p1, Polynom p2)
103: {
104:     return p1 - (p1 / p2) * p2;
105: }
106: 
107: // additional helper operators
108: public static Polynom operator* (Polynom p, double d)
109: {
110:     if (d == 0.0)
111:         return new Polynom();
112: 
113:     Polynom tmp = (Polynom) p.Clone();
114:     for (int i = 0; i < tmp.coefficients.Count; i++)
115:         tmp.coefficients[i] *= d;
116:     return tmp;
117: }
118: 
119: public static Polynom operator* (double d, Polynom p)
120: {
121:     return p * d;
122: }
123: 
124: // comparison operators
125: public static bool operator== (Polynom p1, Polynom p2)
126: {
127:     return p1.CompareTo(p2) == 0;
128: }
129: 
130: public static bool operator!= (Polynom p1, Polynom p2)
131: {
132:     return !(p1 == p2);
133: }
134: 
135: public static bool operator< (Polynom p1, Polynom p2)
136: {
137:     return p1.CompareTo(p2) == -1;
138: }
139: 
140: public static bool operator<= (Polynom p1, Polynom p2)
141: {
142:     return (p1 < p2) || (p1 == p2);
143: }
144: 
145: public static bool operator> (Polynom p1, Polynom p2)
146: {
147:     return !(p1 <= p2);
148: }
149: 
150: public static bool operator>= (Polynom p1, Polynom p2)
151: {
152:     return !(p1 < p2);
153: }

Beispiel 2. Klasse Polynom: Arithmetische Operatoren und Vergleiche.


Ohne Berücksichtigung des .NET-Umfelds wie der geerbte Vertrag mit der universellen Basisklasse Object oder die sinnvolle Ergänzung von Standardschnittstellen ist eine Klassenimplementierung nicht vollständig. Im Falle der Klasse Polynom bietet es sich an, einen Vertrag mit den beiden Schnittstellen ICloneable und IComparable<Polynom> einzugehen (Listing 3):

001: // modifying contract with base class 'Object'
002: public override bool Equals (Object o)
003: {
004:     if (o == null)
005:         return false;
006: 
007:     Type typ = this.GetType();
008:     if (! typ.Equals(o.GetType()))
009:         return false;
010: 
011:     Polynom p = (Polynom)o;
012:     if (this.Rank != p.Rank)
013:         return false;
014: 
015:     for (int i = 0; i < this.coefficients.Count; i++)
016:         if (this.coefficients[i] != p.coefficients[i])
017:             return false;
018: 
019:     return true;
020: }
021: 
022: public override String ToString()
023: {
024:     StringBuilder sb = new StringBuilder();
025: 
026:     for (int i = this.coefficients.Count - 1; i >= 0; i--)
027:     {
028:         if (this.coefficients[i] == 0.0 && this.coefficients.Count > 1)
029:             continue;
030: 
031:         if (i < this.coefficients.Count - 1)
032:             if (this.coefficients[i] > 0.0)
033:                 sb.Append ('+');
034: 
035:         if (this.coefficients[i] != 1 && this.coefficients[i] != -1)
036:         {
037:             sb.Append (this.coefficients[i]);
038:         }
039:         else if (i > 0)
040:         {
041:             if (this.coefficients[i] == -1)
042:                 sb.Append ('-');
043:         }
044:         else
045:             sb.Append (this.coefficients[i]);
046: 
047:         if (i > 0)
048:         {
049:             sb.Append("x^");
050:             sb.Append(i);
051:         }
052:     }
053: 
054:     return sb.ToString();
055: }
056: 
057: // just to remove compiler warning
058: public override int GetHashCode()
059: {
060:     return this.coefficients.GetHashCode();
061: }
062: 
063: // implementation of interface 'ICloneable'
064: public Object Clone()
065: {
066:     return new Polynom(this.coefficients);
067: }
068: 
069: // implementation of interface 'IComparable<Polynom>'
070: public int CompareTo (Polynom p)
071: {
072:     if (this.Rank < p.Rank)
073:         return -1;
074:     if (this.Rank > p.Rank)
075:         return 1;
076: 
077:     for (int i = this.Rank; i >= 0; i--)
078:     {
079:         if (this.coefficients[i] < p.coefficients[i])
080:             return -1;
081:         if (this.coefficients[i] > p.coefficients[i])
082:             return 1;
083:     }
084: 
085:     return 0;
086: }

Beispiel 3. Klasse Polynom: Kontrakte mit Basisklasse Object und zu Schnittstellen.


Es fehlen noch einige Hilfsmethoden, zum Beispiel RemoveLeadingZeros oder auch die Methode Horner. Sie werden überrascht sein, mit welch geringem Aufwand das Hornerschema programmiersprachlich umsetzbar ist, siehe die Zeilen 2 bis 8 von Listing 4:

01: // private helper methods
02: private double Horner(double x)
03: {
04:     double y = this.coefficients[this.Rank];
05:     for (int i = this.Rank - 1; i >= 0; i--)
06:         y = this.coefficients[i] + y * x;
07:     return y;
08: }
09: 
10: private void RemoveLeadingZeros ()
11: {
12:     while (!this.IsZero && this.coefficients[this.coefficients.Count - 1] == 0.0)
13:         this.coefficients.RemoveAt(this.coefficients.Count - 1);
14: }

Beispiel 4. Klasse Polynom: Hilfsmethoden.


Abschließend finden Sie zwei Beispiele zur Multiplikation und Division vor:

Beispiel: Polynommultiplikation

double[] coeffs1 = { 2, -4, 0, 3 };
Polynom p1 = new Polynom(coeffs1);
Console.WriteLine("p1:      {0}", p1.ToString());

double[] coeffs2 = { 3, 3, 5 };
Polynom p2 = new Polynom(coeffs2);
Console.WriteLine("p2:      {0}", p2.ToString());

Polynom p3 = p1 * p2;
Console.WriteLine("p1 * p2: {0}", p3.ToString());
Console.WriteLine();

Ausgabe:

p1:      3x^3-4x^1+2
p2:      5x^2+3x^1+3
p1 * p2: 15x^5+9x^4-11x^3-2x^2-6x^1+6

Beispiel: Polynomdivision

double[] values1 = { 4, -2, 6, 5, -1, 2 };
Polynom p1 = new Polynom(values1);
Console.WriteLine("p1:      {0}", p1.ToString());

double[] values2 = { 4, 2, 0, 1 };
Polynom p2 = new Polynom(values2);
Console.WriteLine("p2:      {0}", p2.ToString());

Polynom p3 = p1 / p2;
Console.WriteLine("p1 / p2: {0}", p3.ToString());

Ausgabe:

p1:      2x^5-x^4+5x^3+6x^2-2x^1+4
p2:      x^3+2x^1+4
p1 / p2: 2x^2-x^1+1