Polynome

1. Einleitung

Gegenstand dieser Aufgabe sind Polynomfunktionen, kurz auch Polynome genannt. Formal ist ein Polynom als 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 (Instanzvariablen, Konstruktoren, Methoden, inklusive getter- und setter-Methoden, Operatoren usw.) zur Definition einer Klasse in C++ in Anspruch nimmt.

2. Konstruktoren und getter-/setter-Methoden

Die Konstruktoren und getter-/setter-Methoden der Klasse Polynom finden Sie in Tabelle 1 genauer spezifiziert vor:

Element

Beschreibung

Standardkonstruktor

Polynom ();

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

P0(x) = 0.

Benutzerdefinierter Konstruktor

Polynom (double coefficients[], int count);

Dieser benutzerdefinierte Konstruktor legt ein Polynom mit den Koeffizienten des Arrays coefficients an. Die Länge des Arrays ist im zweiten Parameter count zu übergeben. Das erste Element des Arrays ist dem niederwertigsten Koeffizienten zuzuordnen, das letzte dem höchstwertigen.

Beachte: Der Grad dieses Polynoms besitzt offensichtlich den Wert count - 1!

Beispiel:

double coeffs[] = { -5.0, +6.0, -7.0 };
Polynom p (coeffs, 3);

getter-Methode Rank

int Rank () const;

Liefert den Grad des Polynoms zurück.

Beispiel:

double coeffs[] = { -5.0, +6.0, -7.0 };
Polynom p (coeffs, 3);
cout << p.Rank() << endl;

Ausgabe:

2

getter-Methode IsZero

bool IsZero () const;

Liefert den Wert true zurück, wenn das aktuelle Polynom das Null-Polynom ist, andernfalls false.

Beispiel:

Polynom p;
cout << p << " -- " << "IsZero: " << p.IsZero() << endl;

double coeffs[] = { 1.0 };
Polynom p1 = Polynom (coeffs, 1);
cout << p1 << " -- " << "IsZero: " << p1.IsZero() << endl;

Ausgabe:

0 -- IsZero: 1
1 -- IsZero: 0

Tabelle 1. Konstruktoren/Destruktor und getter-Methoden der Klasse Polynom.


Für die Ausgabe eines Polynoms auf der Konsole implementieren Sie den Ausgabeoperator << geeignet:

Operator

Beschreibung

Operator <<

friend ostream& operator<< (ostream& os, const Polynom& p);

Gibt das Polynom p auf der Konsole aus.

Beispiel:

double coeffs[] = { 2.0, -4.0, 0.0, 3.0 };
Polynom p (coeffs, 4);
cout << p << endl;

Ausgabe:

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

oder etwas eleganter

3x^3-4x^1+2

Tabelle 2. Ausgabeoperator << der Klasse Polynom.

3. Operatoren

Polynome besitzen eine Reihe zentraler Operatoren und Methoden, um sie beispielsweise zu addieren oder zu multiplizieren oder aber um ihren Wert für ein bestimmtes Argument zu berechnen. Im Folgenden finden Sie einige Wiederholungen der Grundlagen von Polynomen vor.

Die Addition eines Polynoms des Grades n mit einem Polynom des Grades kleiner-gleich m ergibt ein Polynom des Grades Max(n, m). Die Koeffizienten des Ergebnispolynoms werden jeweils durch Addition des Koeffizienten ai des einen Polynoms mit dem passenden Koeffizienten bi des anderen Polynoms gebildet. 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.

Analog zur Addition von Polynomen ist ihre Subtraktion definiert, es werden einfach nur die entsprechenden Koeffizienten voneinander subtrahiert.

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. Das Produkt der Polynome des letzten Beispiels lautet:

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

Im Prinzip können Sie das Multiplizieren zweier Polynome auch als Ausmultiplizieren von Klammern ansehen:

   (3x3 - 4x + 2) * (5x2 + 3x + 3)

= 15x5 + 9x4 + 9x3 - 20x3 - 12x2 - 12x + 10x2 + 6x + 6

= 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:

Damit kommen wir zur Auswertung des Polynoms an einer bestimmten Stelle x. Um uns unnötige Berechnungen von Potenzen zu ersparen, berechnen wir den Wert mit dem sogenannten Horner-Schema. Die Arbeitsweise des Horner-Schemas kann man leicht erkennen, wenn wir es konkret für Polynome bis zum dritten Grad einmal exemplarisch betrachten:

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. An Hand dieses recht einfachen Beispiels sollte die Arbeitsweise des Horner-Schemas erkennbar geworden sein, weitere Erläuterungen finden Sie in der einschlägigen Literatur vor.

Abschließend treffen wir eine Aussage zum Vergleich zweier Polynome: 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.

Informationen bezüglich der einzelnen C++-Operatorensignaturen der soeben betrachteten Polynomfunktionen finden Sie nun in Tabelle 3 vor:

Operator

Beschreibung

Operator +

friend Polynom operator+ (const Polynom& p1, const Polynom& p2);

Addition zweier Polynome.

Beispiel:

double coeffs1[] = { 2.0, -4.0, 0.0, 3.0 };
Polynom p1 (coeffs1, 4);
cout << p1 << endl;

double coeffs2[] = { 3.0, 3.0, 5.0 };
Polynom p2 (coeffs2, 3);
cout << p2 << endl;

Polynom p3 = p1 + p2;
cout << p3 << endl;

Ausgabe:

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

Operator -

friend Polynom operator- (const Polynom& p1, const Polynom& p2);

Subtraktion zweier Polynome.

Beispiel:

double coeffs1[] = { 2.0, -4.0, 0.0, 3.0 };
Polynom p1 (coeffs1, 4);
cout << p1 << endl;

double coeffs2[] = { 3.0, 3.0, 5.0 };
Polynom p2 (coeffs2, 3);
cout << p2 << endl;

Polynom p3 = p1 - p2;
cout << p3 << endl;

Ausgabe:

3x^3-4x^1+2
5x^2+3x^1+3
3x^3-5x^2-7x^1-1

Operator *

friend Polynom operator* (const Polynom& p1, const Polynom& p2);

Multiplikation zweier Polynome.

Beispiel:

double coeffs1[] = { 2.0, -4.0, 0.0, 3.0 };
Polynom p1 (coeffs1, 4);
cout << p1 << endl;

double coeffs2[] = { 3.0, 3.0, 5.0 };
Polynom p2 (coeffs2, 3);
cout << p2 << endl;

cout << p1*p2 << endl;

Ausgabe:

3x^3-4x^1+2
5x^2+3x^1+3
15x^5+9x^4-11x^3-2x^2-6x^1+6

Operator /

friend Polynom operator/ (const Polynom& p1, const Polynom& p2);

Division zweier Polynome. Hinweis: Diese Teilaufgabe kann dadurch vereinfacht werden, wenn Sie die Klasse Polynom um zwei Hilfsmethoden sowie zwei Hilfsoperatoren ergänzen:

  • void MultiplyConst (double d);

    Multiplikation eines Polynoms mit der Konstanten d.

  • void MultiplyX (int k);

    Multiplikation eines Polynoms mit x oder einer Potenz von x. Der Parameter k spezifiziert den Exponenten von x, beschreibt also den Term xk.

  • friend Polynom operator* (const Polynom& p, double d);
    friend Polynom operator* (double d, const Polynom& p);

    Multiplikation eines Polynoms mit der Konstanten d in Operatorenschreibweise.

Beispiel:

double values1[] = { 4, -2, 6, 5, -1, 2 };
Polynom p1 (values1, 6);
cout << "p1:    " << p1 << endl;

double values2[] = { 4, 2, 0, 1 };
Polynom p2 (values2, 4);
cout << "p2:    " << p2 << endl;

Polynom p3 = p1 / p2;
cout << "p1/p2: " << p3 << endl;

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

Operator %

friend Polynom operator% (const Polynom& p1, const Polynom& p2);

Rest bei Division zweier Polynome.

Beispiel:

double values1[] = { 0, -4, 8, 10, 3 };
Polynom p1 (values1, 5);
cout << "p1:    " << p1 << endl;

double values2[] = { 0, 4, 3 };
Polynom p2 (values2, 3);
cout << "p2:    " << p2 << endl;

Polynom p3 = p1 % p2;
cout << "p1%p2: " << p3 << endl;

Ausgabe:

p1:    3x^4+10x^3+8x^2-4x^1
p2:    3x^2+4x^1
p1%p2: -4x^1

Operatoren +=, -=, *=, /= und %=

friend Polynom& operator+= (Polynom& p1, const Polynom& p2);
friend Polynom& operator-= (Polynom& p1, const Polynom& p2);
friend Polynom& operator*= (Polynom& p1, const Polynom& p2);
friend Polynom& operator/= (Polynom& p1, const Polynom& p2);
friend Polynom& operator%= (Polynom& p1, const Polynom& p2);

Arithmetische Operatoren in der Wertzuweisungsform.

Beispiel:

double coeffs1[] = { 1.0, 2.0, 3.0 };
Polynom p1 (coeffs1, 3);
cout << p1 << endl;

double coeffs2[] = { 3.0, 2.0, 1.0 };
Polynom p2 (coeffs2, 3);
cout << p2 << endl;

p1 += p2;
cout << p1 << endl;
p1 -= p2;
cout << p1 << endl;
p1 *= p2;
cout << p1 << endl;
p1 /= p2;
cout << p1 << endl;
p1 %= p2;
cout << p1 << endl;

Ausgabe:

3x^2+2x^1+1
x^2+2x^1+3
4x^2+4x^1+4
3x^2+2x^1+1
3x^4+8x^3+14x^2+8x^1+3
3x^2+2x^1+1
-4x^1-8

Index-Operator []

Funktionsaufruf-Operator ()

double operator[] (double x);
double operator() (double x);

Um die mathematische Schreibweise für die Auswertung eines Polynoms p an der Stelle y nachzuahmen, bieten sich in C++ gleich zwei Operatoren an: Der Index-Operator [] sowie der Funktionsaufruf-Operator (). Letzterer ist möglicherweise etwas schwerer zu verstehen oder nachzuvollziehen, spiegelt dafür die mathematische Schreibweise exakt wieder. Der Index-Operator könnte für einen C++-Programmierer etwas intuitiver sein, weicht dafür etwas vom Original ab. Ausnahmsweise möchte ich Sie mit der Entscheidung, für welche Variante Sie sich entscheiden, hier nicht beeinflussen. Technisch gesehen sind in der Implementierung beide Varianten weitestgehend identisch, so dass ich sie beide in die Polynom-Klasse mit aufgenommen habe. Bilden Sie sich Ihr eigenes Urteil an Hand folgender Beispiele:

Beispiel:

double coeffs[] = { 2.0, -4.0, 0.0, 3.0 };
Polynom p (coeffs, 4);
cout << "p: " << p << endl << endl;

// values of p at 0.0, 1.0 and 2.0, using array subscripting operator
cout << "p(0.0) = " << p[0.0] << endl;
cout << "p(1.0) = " << p[1.0] << endl;
cout << "p(2.0) = " << p[2.0] << endl;

// values of p at 0.0, 1.0 and 2.0, using function call operator
cout << "p(0.0) = " << p(0.0) << endl;
cout << "p(1.0) = " << p(1.0) << endl;
cout << "p(2.0) = " << p(2.0) << endl;

Ausgabe:

p: 3x^3-4x^1+2

p(0.0) = 2
p(1.0) = 1
p(2.0) = 18
p(0.0) = 2
p(1.0) = 1
p(2.0) = 18

Operatoren ==, !=, <, <=, > und >=

friend bool operator== (const Polynom& p1, const Polynom& p2);
friend bool operator!= (const Polynom& p1, const Polynom& p2);
friend bool operator<  (const Polynom& p1, const Polynom& p2);
friend bool operator<= (const Polynom& p1, const Polynom& p2);
friend bool operator>  (const Polynom& p1, const Polynom& p2);
friend bool operator>= (const Polynom& p1, const Polynom& p2);

Test zweier Polynome auf Gleichheit, Ungleichheit sowie auf größer(-gleich) und kleiner(-gleich).

Beispiel:

double coeffs1[] = { 2.0, -4.0, 0.0, 3.0 };
Polynom p1 (coeffs1, 4);
double coeffs2[] = { 3.0, 3.0, 5.0 };
Polynom p2 (coeffs2, 3);

cout << "p1 == p2: " << (p1 == p2) << endl;
cout << "p1 != p2: " << (p1 != p2) << endl;
cout << "p1 <  p2: " << (p1 <  p2) << endl;
cout << "p1 <= p2: " << (p1 <= p2) << endl;
cout << "p1 >  p2: " << (p1 >  p2) << endl;
cout << "p1 >= p2: " << (p1 >= p2) << endl;

Ausgabe:

p1 == p2: 0
p1 != p2: 1
p1 <  p2: 0
p1 <= p2: 0
p1 >  p2: 1
p1 >= p2: 1

Tabelle 3. Operatoren der Klasse Polynom.

4. Lösung

Quellcode: Siehe auch https://github.com/peterloos/Cpp_Polynom

01: class Polynom
02: {
03: private:
04:     double* m_coefficients;
05:     int     m_count;
06: 
07: public:
08:     // c'tors / d'tor
09:     Polynom  ();
10:     Polynom  (double coefficients[], int count);
11:     Polynom  (const Polynom&);
12:     ~Polynom ();
13: 
14: public:
15:     // getter
16:     int Rank () const;
17:     bool IsZero () const;
18: 
19:     // assignment operator
20:     Polynom& operator= (const Polynom& p);
21: 
22:     // unary mathematical operators
23:     friend Polynom operator+ (const Polynom& p);
24:     friend Polynom operator- (const Polynom& p);
25: 
26:     // binary mathematical operators
27:     friend Polynom operator+ (const Polynom& p1, const Polynom& p2);
28:     friend Polynom operator- (const Polynom& p1, const Polynom& p2);
29:     friend Polynom operator* (const Polynom& p1, const Polynom& p2);
30:     friend Polynom operator/ (const Polynom& p1, const Polynom& p2);
31:     friend Polynom operator% (const Polynom& p1, const Polynom& p2);
32: 
33:     // binary mathematical assignment operators
34:     friend Polynom& operator+= (Polynom& p1, const Polynom& p2);
35:     friend Polynom& operator-= (Polynom& p1, const Polynom& p2);
36:     friend Polynom& operator*= (Polynom& p1, const Polynom& p2);
37:     friend Polynom& operator/= (Polynom& p1, const Polynom& p2);
38:     friend Polynom& operator%= (Polynom& p1, const Polynom& p2);
39: 
40:     // comparison operators
41:     friend bool operator== (const Polynom& p1, const Polynom& p2);
42:     friend bool operator!= (const Polynom& p1, const Polynom& p2);
43:     friend bool operator<  (const Polynom& p1, const Polynom& p2);
44:     friend bool operator<= (const Polynom& p1, const Polynom& p2);
45:     friend bool operator>  (const Polynom& p1, const Polynom& p2);
46:     friend bool operator>= (const Polynom& p1, const Polynom& p2);
47: 
48:     // index operator
49:     double operator[] (double x);
50: 
51:     // function call operator
52:     double operator() (double x);
53: 
54:     // output
55:     friend ostream& operator<< (ostream& os, const Polynom& p);
56: 
57: private:
58:     // private helper operators
59:     friend Polynom operator* (const Polynom& p, double d);
60:     friend Polynom operator* (double d, const Polynom& p);
61: 
62:     // private helper methods
63:     void MultiplyX ();
64:     void MultiplyX (int k);
65: 
66:     // horner scheme
67:     double Compute (double x);
68: };

Beispiel 1. Klasse Polynom: Schnittstelle.


001: #include <iostream>
002: using namespace std;
003: 
004: #include "Polynom.h"
005: 
006: // c'tors
007: Polynom::Polynom ()
008: {
009:     // default c'tor: create zero polynom
010:     m_count = 1;
011:     m_coefficients = new double[1];
012:     m_coefficients[0] = 0.0;
013: }
014: 
015: Polynom::Polynom (const Polynom& p)
016: {
017:     // copy c'tor
018:     m_count = p.m_count;
019:     m_coefficients = new double[p.m_count];
020:     for (int i = 0; i < m_count; i++)
021:         m_coefficients[i] = p.m_coefficients[i];
022: }
023: 
024: Polynom::Polynom (double coefficients[], int count)
025: {
026:     // remove leading zeros
027:     int max = count - 1;
028:     while (max > 0 && coefficients[max] == 0)
029:         max --;
030: 
031:     m_count = max + 1;
032:     m_coefficients = new double[m_count];
033: 
034:     for (int i = 0; i < m_count; i ++)
035:         m_coefficients[i] = coefficients[i];
036: }
037: 
038: // d'tor
039: Polynom::~Polynom ()
040: {
041:     delete[] m_coefficients;
042: }
043: 
044: // getter
045: int Polynom::Rank () const
046: {
047:     return m_count - 1;
048: }
049: 
050: bool Polynom::IsZero () const
051: {
052:     return m_count == 1 && m_coefficients[0] == 0;
053: }
054: 
055: // unary mathematical operators + and -
056: Polynom operator+ (const Polynom& p)
057: {
058:     return Polynom (p);
059: }
060: 
061: Polynom operator- (const Polynom& p)
062: {
063:     Polynom tmp (p);
064:     for (int i = 0; i < tmp.m_count; i++)
065:         tmp.m_coefficients[i] *= -1.0;
066:     return tmp;
067: }
068: 
069: // binary mathematical operators +, -, *, / and %
070: Polynom operator+ (const Polynom& p1, const Polynom& p2)
071: {
072:     int count = (p1.m_count <= p2.m_count) ? p2.m_count : p1.m_count;
073: 
074:     // create array of coefficients
075:     double* coefficients = new double[count];
076:     for (int i = count - 1; i >= 0; i --)
077:     {
078:         double coeff = 0.0;
079:         if (i < p1.m_count)
080:             coeff += p1.m_coefficients[i];
081:         if (i < p2.m_count)
082:             coeff += p2.m_coefficients[i];
083:         coefficients[i] = coeff;
084:     }
085: 
086:     // create result polynom
087:     Polynom tmp (coefficients, count);
088: 
089:     // release temporary coefficients array
090:     delete[] coefficients;
091: 
092:     return tmp;
093: }
094: 
095: Polynom operator- (const Polynom& p1, const Polynom& p2)
096: {
097:     Polynom tmp = - p2;
098:     tmp = p1 + tmp;
099:     return tmp;
100: }
101: 
102: Polynom operator* (const Polynom &p1, const Polynom &p2)
103: {
104:     // create array of coefficients
105:     int count = p1.m_count + p2.m_count -1;
106:     double* coefficients = new double[count];
107: 
108:     // clear coefficients array
109:     for (int i = 0; i < count; i ++)
110:         coefficients[i] = 0.0;
111: 
112:     // compute coefficients of polynom product
113:     for (int i = p1.m_count - 1; i >= 0; i--)
114:         for (int j = p2.m_count - 1; j >= 0; j--)
115:             coefficients[i + j] +=
116:                 p1.m_coefficients[i] * p2.m_coefficients[j];
117: 
118:     // create result polynom
119:     Polynom result (coefficients, count);
120: 
121:     // delete temporary array of coefficients
122:     delete[] coefficients;
123: 
124:     return result;
125: }
126: 
127: Polynom operator/ (const Polynom& p1, const Polynom& p2)
128: {
129:     if (p1.m_count < p2.m_count)  // degree of numerator polynom is less than
130:         return Polynom();         // degree of denominator polynom
131: 
132:     // need copies of arguments
133:     Polynom tmp1 = p1;
134:     Polynom tmp2 = p2;
135: 
136:     // create coefficients array of result polynom
137:     int count = p1.m_count - p2.m_count + 1;
138:     double* rescoeff = new double[count];
139: 
140:     // clear coefficients array
141:     for (int i = 0; i < count; i ++)
142:         rescoeff[i] = 0.0;
143: 
144:     // apply algorithm of polynom division
145:     for (int i = count - 1; i >= 0 ; i--)
146:     {
147:         // premature end of division reached (comparing degrees)
148:         if (tmp1.m_count < p2.m_count)
149:             break;
150: 
151:         // calculate next coefficient of result polynom
152:         double coeff =
153:             tmp1.m_coefficients[tmp1.m_count - 1] /
154:             tmp2.m_coefficients[tmp2.m_count - 1];
155: 
156:         // multiply denominator polynom with coefficient
157:         tmp2 = tmp2 * coeff;
158: 
159:         // calculate difference of ranks
160:         int diffRank = tmp1.m_count - p2.m_count;
161: 
162:         // multiply denominator polynom with one ore more 'x'
163:         tmp2.MultiplyX(diffRank);
164: 
165:         // subtract denominator polynom from numerator polynom
166:         tmp1 = tmp1 - tmp2;
167: 
168:         // poke calculated coefficient into result polynom
169:         rescoeff[diffRank] = coeff;
170: 
171:         // restore denominator polynom
172:         tmp2 = p2;
173:     }
174: 
175:     return Polynom(rescoeff, count); 
176: }
177: 
178: Polynom operator% (const Polynom& p1, const Polynom& p2)
179: {
180:     return p1 - (p1 / p2) * p2;
181: }
182: 
183: // binary mathematical assignment operators +=, -=, *=, /= and %=
184: Polynom& operator+= (Polynom& p1, const Polynom& p2)
185: {
186:     p1 = p1 + p2;
187:     return p1;
188: }
189: 
190: Polynom& operator-= (Polynom& p1, const Polynom& p2)
191: {
192:     p1 = p1 - p2;
193:     return p1;
194: }
195: 
196: Polynom& operator*= (Polynom& p1, const Polynom& p2)
197: {
198:     p1 = p1 * p2;
199:     return p1;
200: }
201: 
202: Polynom& operator/= (Polynom& p1, const Polynom& p2)
203: {
204:     p1 = p1 / p2;
205:     return p1;
206: }
207: 
208: Polynom& operator%= (Polynom& p1, const Polynom& p2)
209: {
210:     p1 = p1 % p2;
211:     return p1;
212: }
213: 
214: 
215: 
216: 
217: // horner scheme
218: double Polynom::Compute (double x)
219: {
220:     double y = m_coefficients[m_count - 1];        
221:     for (int i = m_count - 2; i >= 0; i--) 
222:         y = m_coefficients[i] + y * x;
223:     return y;
224: }
225: 
226: // apply horner scheme, using array subscripting operator
227: double Polynom::operator[](double x)
228: {
229:     return Compute (x);
230: }
231: 
232: // apply horner scheme, using function call operator
233: double Polynom::operator() (double x)
234: {
235:     return Compute (x);
236: }
237: 
238: // comparison operators
239: bool operator== (const Polynom& p1, const Polynom& p2)
240: {
241:     if (p1.m_count != p2.m_count)
242:         return false;
243: 
244:     for (int i = 0; i < p1.m_count; i ++)
245:         if (p1.m_coefficients[i] != p2.m_coefficients[i])
246:             return false;
247: 
248:     return true;
249: }
250: 
251: bool operator!= (const Polynom& p1, const Polynom& p2)
252: {
253:     return ! (p1 == p2);
254: }
255: 
256: bool operator<  (const Polynom& p1, const Polynom& p2)
257: {
258:     if (p1.m_count < p2.m_count)
259:         return true;
260: 
261:     if (p1.m_count > p2.m_count)
262:         return false;
263: 
264:     for (int i = p1.m_count - 1; i >= 0; i --)
265:     {
266:         if (p1.m_coefficients[i] < p2.m_coefficients[i])
267:             return true;
268:         if (p1.m_coefficients[i] > p2.m_coefficients[i])
269:             return false;
270:     }
271: 
272:     return false;
273: }
274: 
275: bool operator<= (const Polynom& p1, const Polynom& p2)
276: {
277:     return (p1 < p2) || (p1 == p2);
278: }
279: 
280: bool operator>  (const Polynom& p1, const Polynom& p2)
281: {
282:     return ! (p1 <= p2);
283: }
284: 
285: bool operator>= (const Polynom& p1, const Polynom& p2)
286: {
287:     return ! (p1 < p2);
288: }
289: 
290: // output
291: ostream& operator<< (ostream& os, const Polynom& p)
292: {
293:     for (int i = p.m_count - 1; i >= 0; i --)
294:     {
295:         if (p.m_coefficients[i] == 0.0 && p.m_count > 1)
296:             continue;
297: 
298:         if (i < p.m_count - 1)
299:             if (p.m_coefficients[i] > 0.0)
300:                 os << '+';
301:         
302:         if (p.m_coefficients[i] != 1 && p.m_coefficients[i] != -1)
303:         {
304:             os << p.m_coefficients[i];
305:         }
306:         else if (i > 0)
307:         {
308:             if (p.m_coefficients[i] == -1)
309:                 os << '-';
310:         }
311:         else
312:             os << p.m_coefficients[i];
313: 
314:         if (i > 0)
315:             os << 'x' << '^' << i;
316:     }
317: 
318:     return os;
319: }
320: 
321: // assignment operator
322: Polynom& Polynom::operator= (const Polynom& p)
323: {
324:     if (this == &p)
325:         return *this;
326: 
327:     // release left side
328:     delete[] m_coefficients;
329: 
330:     // copy right side
331:     m_count = p.m_count;
332:     m_coefficients = new double[p.m_count];
333:     for (int i = 0; i < m_count; i++)
334:         m_coefficients[i] = p.m_coefficients[i];
335: 
336:     return *this;
337: }
338: 
339: // private helper operators
340: Polynom operator* (double d, const Polynom& p)
341: {
342:     Polynom q = p;
343:     for (int i = 0; i < p.m_count; i ++)
344:         q.m_coefficients[i] *= d;
345:     return q;
346: }
347: 
348: Polynom operator* (const Polynom& p, double d)
349: {
350:     return d * p;
351: }
352: 
353: // private helper methods
354: void Polynom::MultiplyX ()
355: {
356:     // create new array of coefficients
357:     double* tmp = new double[m_count + 1];
358: 
359:     // compute new coefficients
360:     tmp[0] = 0.0;
361:     for (int i = 1; i <= m_count; i ++)
362:         tmp[i] = m_coefficients[i - 1];
363: 
364:     // switch coefficients buffer
365:     delete[] m_coefficients;
366:     m_coefficients = tmp;
367:     m_count ++;
368: }
369: 
370: void Polynom::MultiplyX (int k)
371: {
372:     for (int i = 0; i < k; i ++) 
373:         MultiplyX ();
374: }

Beispiel 2. Klasse Polynom: Implementierung.