1 package practice;
2 //http://introcs.cs.princeton.edu/java/92symbolic/Polynomial.java.html
3 /*************************************************************************
4 * Compilation: javac Polynomial.java
5 * Execution: java Polynomial
6 *
7 * Polynomials with integer coefficients.
8 *
9 * % java Polynomial
10 * zero(x) = 0
11 * p(x) = 4x^3 + 3x^2 + 2x + 1
12 * q(x) = 3x^2 + 5
13 * p(x) + q(x) = 4x^3 + 6x^2 + 2x + 6
14 * p(x) * q(x) = 12x^5 + 9x^4 + 26x^3 + 18x^2 + 10x + 5
15 * p(q(x)) = 108x^6 + 567x^4 + 996x^2 + 586
16 * 0 - p(x) = -4x^3 - 3x^2 - 2x - 1
17 * p(3) = 142
18 * p'(x) = 12x^2 + 6x + 2
19 * p''(x) = 24x + 6
20 *
21 *************************************************************************/
22 public class Polynomial {
23 private int[] coef; //coefficients 系数
24 private int deg;//degree of polynomial (0 for the zero polynomial)
25
26 //a*x^b
27 public Polynomial(int a, int b){
28 coef = new int[b+1];
29 coef[b] = a;
30 deg = degree();
31 }
32
33 // return the degree of this polynomial (0 for the zero polynomial)
34 public int degree(){
35 int d = 0;
36 for(int i = 0; i<coef.length; i++)
37 if(coef[i]!=0)
38 d = i;
39
40 return d;
41 }
42
43 //return c = a+b
44 public Polynomial plus(Polynomial b){
45 Polynomial a = this;
46 Polynomial c = new Polynomial(0, Math.max(a.deg, b.deg));
47 for(int i = 0; i <= a.deg; i++)
48 c.coef[i] += a.coef[i];
49 for(int i = 0; i <= b.deg; i++)
50 c.coef[i] += b.coef[i];
51 c.deg = c.degree();
52 return c;
53 }
54
55 // return (a - b)
56 public Polynomial minus(Polynomial b) {
57 Polynomial a = this;
58 Polynomial c = new Polynomial(0, Math.max(a.deg, b.deg));
59 for (int i = 0; i <= a.deg; i++) c.coef[i] += a.coef[i];
60 for (int i = 0; i <= b.deg; i++) c.coef[i] -= b.coef[i];
61 c.deg = c.degree();
62 return c;
63 }
64
65 // return (a * b)
66 public Polynomial times(Polynomial b) {
67 Polynomial a = this;
68 Polynomial c = new Polynomial(0, a.deg + b.deg);
69 for (int i = 0; i <= a.deg; i++)
70 for (int j = 0; j <= b.deg; j++)
71 c.coef[i+j] += (a.coef[i] * b.coef[j]);
72 c.deg = c.degree();
73 return c;
74 }
75
76 // return a(b(x)) - compute using Horner's method
77 public Polynomial compose(Polynomial b) {
78 Polynomial a = this;
79 Polynomial c = new Polynomial(0, 0);
80 for (int i = a.deg; i >= 0; i--) {
81 Polynomial term = new Polynomial(a.coef[i], 0);
82 c = term.plus(b.times(c));
83 }
84 return c;
85 }
86
87
88 // do a and b represent the same polynomial?
89 public boolean eq(Polynomial b) {
90 Polynomial a = this;
91 if (a.deg != b.deg) return false;
92 for (int i = a.deg; i >= 0; i--)
93 if (a.coef[i] != b.coef[i]) return false;
94 return true;
95 }
96
97
98 // use Horner's method to compute and return the polynomial evaluated at x
99 public int evaluate(int x) {
int p = 0;
for (int i = deg; i >= 0; i--)
p = coef[i] + (x * p);
return p;
}
// differentiate this polynomial and return it
public Polynomial differentiate() {
if (deg == 0) return new Polynomial(0, 0);
Polynomial deriv = new Polynomial(0, deg - 1);
deriv.deg = deg - 1;
for (int i = 0; i < deg; i++)
deriv.coef[i] = (i + 1) * coef[i + 1];
return deriv;
}
public String toString(){
if(deg == 0)
return "" + coef[0];
if(deg == 1)
return coef[1] + "x + " + coef[0];
String s = coef[deg] + "x^" + deg;
for(int i = deg-1; i >= 0; i--){
if(coef[i] == 0)
continue;
else if(coef[i] > 0)
s = s + " + " + ( coef[i]);
else if(coef[i] < 0)
s = s + " - " + (-coef[i]);
if(i== 1)
s = s + "x";
else if(i > 1)
s = s +"x^" + i;
}
return s;
}
public static void main(String[] args) {
Polynomial zero = new Polynomial(0, 0);
Polynomial p1 = new Polynomial(4, 3);
Polynomial p2 = new Polynomial(3, 2);
Polynomial p3 = new Polynomial(1, 0);
Polynomial p4 = new Polynomial(2, 1);
Polynomial p = p1.plus(p2).plus(p3).plus(p4); // 4x^3 + 3x^2 + 1
Polynomial q1 = new Polynomial(3, 2);
Polynomial q2 = new Polynomial(5, 0);
Polynomial q = q1.plus(q2); // 3x^2 + 5
Polynomial r = p.plus(q);
// Polynomial s = p.times(q);
// Polynomial t = p.compose(q);
System.out.println("zero(x) = " + zero);
System.out.println("p(x) = " + p);
System.out.println("q(x) = " + q);
System.out.println("p(x) + q(x) = " + r);
// System.out.println("p(x) * q(x) = " + s);
// System.out.println("p(q(x)) = " + t);
// System.out.println("0 - p(x) = " + zero.minus(p));
// System.out.println("p(3) = " + p.evaluate(3));
// System.out.println("p'(x) = " + p.differentiate());
// System.out.println("p''(x) = " + p.differentiate().differentiate());
}
}