001 package de.hska.java.aufgaben.objekte;
002
003 import de.hska.java.aufgaben.suchen.Funktion;
004
005 /**
006 * Eine reelwertige Polynomfunktion, mit der Werte ausgerechnet und verschiedene
007 * Operationen wie Addition von Polynomen durchgeführt werden können.
008 *
009 * <p>
010 * <a href="http://www.home.hs-karlsruhe.de/~pach0003/informatik_1/aufgaben/objekt_orientierung.html#polynom">Zurück zum Aufgabentext</a>
011 * </p>
012 *
013 *
014 * @author Christian Pape
015 *
016 */
017 public class Polynom implements Funktion {
018
019 private double koeffizienten[] = {0.0}; // Null-Polynom
020
021 /**
022 * Erzeugt ein neues Polynom mit den gegebenen <code>koeffizienten</code>.
023 * Das Polynom ist definiert durch
024 * <pre>
025 * koeffizienten[0] + koeffizienten[1] * x + koeffizienten[2] * x<sup>2</sup> + ... + koeffizienten[n] * x<sup>n</sup>,
026 * </pre>
027 * wobei n = koeffizienten.length - 1 ist.
028 */
029 public Polynom(double [] koeffizienten) {
030 this.koeffizienten = koeffizienten;
031 normalisieren();
032 }
033
034 /**
035 * Erzeugt ein Null-Polynom p, das heisst es gilt: p(x) = 0 für alle x.
036 */
037 public Polynom() {
038 }
039
040 /**
041 * Gibt den Funktionswert dieses Polynoms an Stelle <code>x</code> zurück.
042 * Es wird das Horner-Schema für die Berechnung angewendet, um
043 * Multiplikationsoperationen einzusparen.
044 * Beim Horner-Schema wird x fortlaufend ausgeklammert.
045 * Statt zum Beispiel
046 * <center>
047 * 5 + 2*x - 7*x<sup>2</sup> + 3*x<sup>3</sup>
048 * </center>
049 * mit den Potenzen von x zu berechnen wird
050 * <center>
051 * 5 + x * ( 2 + x * ( -7 + x * 3 ) )
052 * </center>
053 * berechnet.
054 * Zeitaufand ist O(n).
055 */
056 public double f(double x) {
057 double funktionsWert = 0.0;
058
059 for (int i = getGrad(); i >= 0; i--) {
060 funktionsWert *= x;
061 funktionsWert += getKoeffizient(i);
062 }
063
064 return funktionsWert;
065 }
066
067 /**
068 * Addierte dieses Polynom zum gegebenen <code>polynom</code> und
069 * gibt die Summe zurück.
070 */
071 public Polynom addiere(final Polynom polynom) {
072 int maximalerGrad = Math.max(getGrad(), polynom.getGrad());
073 double [] koeffizienten1 = new double[maximalerGrad + 1];
074 Polynom summe = null;
075
076 for (int i = 0; i <= maximalerGrad; i++) {
077 if ( i > getGrad() ) {
078 koeffizienten1[i] = polynom.getKoeffizient(i);
079 } else if (i > polynom.getGrad()) {
080 koeffizienten1[i] = this.getKoeffizient(i);
081 } else {
082 koeffizienten1[i] = this.getKoeffizient(i) + polynom.getKoeffizient(i);
083 }
084 }
085
086 summe = new Polynom(koeffizienten1);
087 summe.normalisieren();
088
089 return summe;
090 }
091
092 /**
093 * Multipliziert dieses Polynom mit dem gegebenen Wert <code>a</code>
094 */
095 public Polynom multiplizeren(double a) {
096 double [] koeffizienten = new double[getGrad() + 1];
097 Polynom polynom = null;
098
099 if ( isNull(a) ) {
100 return new Polynom();
101 } else {
102 for (int i = 0; i <= getGrad(); i++) {
103 koeffizienten[i] = a * this.getKoeffizient(i);
104 }
105 }
106
107 polynom = new Polynom(koeffizienten);
108 polynom.normalisieren();
109
110 return polynom;
111 }
112
113 /**
114 * Prüft, ob vom Grad ab abwärts Koeffizienten 0 sind, sie als
115 * den Grad dieses Polynoms reduzieren würden und entfernt diese.
116 */
117 private void normalisieren() {
118 int maximalerGrad = koeffizienten.length - 1;
119
120 // Den richtigen Grad des Ergebnis berechnen (Koeffizient könnte 0 geworden sein)
121 while ( isNull(koeffizienten[maximalerGrad]) ) {
122 maximalerGrad--;
123 }
124
125 if (maximalerGrad < koeffizienten.length - 1) {
126 double [] koeffizienten1 = new double[maximalerGrad + 1];
127
128 for (int i = 0; i <= maximalerGrad; i++) {
129 koeffizienten1[i] = koeffizienten[i];
130 }
131
132 koeffizienten = koeffizienten1;
133 }
134 }
135
136 /**
137 * Gibt den Grad (den größten Exponenten) dieses Polynoms zurück.
138 */
139 public int getGrad() {
140 return this.koeffizienten.length - 1;
141 }
142
143 /**
144 * Gibt den Koeffizienten dieses Polynoms zurück, der
145 * sich an der angegebenen <code>stelle</code> befindet.
146 * Zum Beispiel ist bei x*x + 2*x + 3, 3 der Koeffizient an
147 * 0-ter Stelle, 2 an 1-ter Stelle.
148 */
149 public double getKoeffizient(int stelle) {
150 return koeffizienten[stelle];
151 }
152
153
154 /**
155 * Gibt true zurück, wenn <code>a</code> sehr, sehr nah bei 0.0 liegt.
156 */
157 private boolean isNull(double a) {
158 return Math.abs(a) < Double.MIN_VALUE * 100;
159 }
160
161 /**
162 * Gibt die erstes Ableitung dieses Polynoms zurück.
163 * Die erste Ableitung eines Polynoms
164 * a<sub>0</sub>x<sup>0</sup> + a<sub>1</sub>x<sup>1</sup> + ... +
165 * a<sub>n-1</sub>x<sup>n-1</sup> + a<sub>n</sub>x<sup>n</sup> ist definiert als
166 * 1 * a<sub>1</sub>x<sup>0</sup> + ... +
167 * (n-1)a<sub>n-1</sub>x<sup>n-2</sup> + n a<sub>n</sub>x<sup>n-1</sup>.
168 */
169 public Polynom getErsteAbleitung() {
170 Polynom ableitung = null;
171
172 if ( getGrad() > 0 ) {
173 double [] koeffizientenDerAbleitung = new double[koeffizienten.length -1];
174 for (int i = 1; i < koeffizienten.length; i++) {
175 koeffizientenDerAbleitung[i-1] = koeffizienten[i] * i;
176 }
177 ableitung = new Polynom(koeffizientenDerAbleitung);
178 } else {
179 ableitung = new Polynom();
180 }
181
182 return ableitung;
183 }
184
185 }