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) { 100 int p = 0; 101 for ( int i = deg; i >= 0; i--) 102 p = coef[i] + (x * p); 103 return p; 104 } 105 106 // differentiate this polynomial and return it 107 public Polynomial differentiate() { 108 if (deg == 0) return new Polynomial(0, 0); 109 Polynomial deriv = new Polynomial(0, deg - 1); 110 deriv.deg = deg - 1; 111 for ( int i = 0; i < deg; i++) 112 deriv.coef[i] = (i + 1) * coef[i + 1]; 113 return deriv; 114 } 115 public String toString(){ 116 if(deg == 0) 117 return "" + coef[0]; 118 if(deg == 1) 119 return coef[1] + "x + " + coef[0]; 120 121 String s = coef[deg] + "x^" + deg; 122 for( int i = deg-1; i >= 0; i--){ 123 if(coef[i] == 0) 124 continue; 125 else if(coef[i] > 0) 126 s = s + " + " + ( coef[i]); 127 else if(coef[i] < 0) 128 s = s + " - " + (-coef[i]); 129 if(i== 1) 130 s = s + "x"; 131 else if(i > 1) 132 s = s +"x^" + i; 133 } 134 return s; 135 } 136 137 public static void main(String[] args) { 138 Polynomial zero = new Polynomial(0, 0); 139 140 Polynomial p1 = new Polynomial(4, 3); 141 Polynomial p2 = new Polynomial(3, 2); 142 Polynomial p3 = new Polynomial(1, 0); 143 Polynomial p4 = new Polynomial(2, 1); 144 Polynomial p = p1.plus(p2).plus(p3).plus(p4); // 4x^3 + 3x^2 + 1 145 146 Polynomial q1 = new Polynomial(3, 2); 147 Polynomial q2 = new Polynomial(5, 0); 148 Polynomial q = q1.plus(q2); // 3x^2 + 5 149 150 151 Polynomial r = p.plus(q); 152 // Polynomial s = p.times(q); 153 // Polynomial t = p.compose(q); 154 155 System.out.println("zero(x) = " + zero); 156 System.out.println("p(x) = " + p); 157 System.out.println("q(x) = " + q); 158 System.out.println("p(x) + q(x) = " + r); 159 // System.out.println("p(x) * q(x) = " + s); 160 // System.out.println("p(q(x)) = " + t); 161 // System.out.println("0 - p(x) = " + zero.minus(p)); 162 // System.out.println("p(3) = " + p.evaluate(3)); 163 // System.out.println("p'(x) = " + p.differentiate()); 164 // System.out.println("p''(x) = " + p.differentiate().differentiate()); 165 } 166 }