/** A class to to test the Polynomial class. */ public class PolynomialTester {
ID: 3857783 • Letter: #
Question
/**
A class to to test the Polynomial class.
*/
public class PolynomialTester
{
public static void main(String[] args)
{
Polynomial p = new Polynomial(new Term(-10, 0));
p.print();
System.out.println(" Expected: - 10.0");
p.add(new Polynomial(new Term(-1, 1)));
p.print();
System.out.println(" Expected: - 1.0x - 10.0");
p.add(new Polynomial(new Term(9, 7)));
p.print();
System.out.println(" Expected: 9.0x^7 - 1.0x - 10.0");
p.add(new Polynomial(new Term(5, 10)));
p.print();
System.out.println(" Expected: 5.0x^10 + 9.0x^7 - 1.0x - 10.0");
Polynomial q = p.multiply(p);
q.print();
System.out.println(" Expected: 25.0x^20 + 90.0x^17 + 81.0x^14 - 10.0x^11 - 100.0x^10 - 18.0x^8 - 180.0x^7 + 1.0x^2 + 20.0x + 100.0");
}
}
Polynomial.java
import java.util.LinkedList;
import java.util.ListIterator;
/**
A class to represent a polynomial.
*/
public class Polynomial
{
. . .
/**
Constructs an empty polynomial
*/
public Polynomial()
{
. . .
}
/**
Constructs a new polynomial with the given term
@param t the term to initialize the polynomial with
*/
public Polynomial(Term t)
{
. . .
}
/**
Adds the polynomial such that the terms are in sorted order
from highest power to lowest
@param p the polynomial to add
*/
public void add(Polynomial p)
{
. . .
}
/**
Multiplies the given polynomial with this one and returns the result
@param p the polynomial to multiply
@return this * p
*/
public Polynomial multiply(Polynomial p)
{
. . .
}
/**
Prints the polynomial "nicely" so that it reads
from highest term to lowest and doesn't have a
leading "+" if the first term is positive.
*/
public void print()
{
. . .
Term.java
}
}
/**
A class to represent an algebraic term.
*/
public class Term
{
private double coefficient;
private int power;
/**
A constructor to initialize a single term with a given coefficient and power
@param coefficent the coefficient
@param power the power
*/
public Term(double coefficient, int power)
{
this.coefficient = coefficient;
this.power = power;
}
/**
@return the coefficient
*/
public double getCoefficient()
{
return coefficient;
}
/**
@return the power
*/
public int getPower()
{
return power;
}
/**
Multiplies two coefficient together and returns the result
@param t the other term
@return this * t as a term
*/
public Term multiply(Term t)
{
return new Term(coefficient * t.coefficient, power + t.power);
}
/**
Adds the term to this term if the powers are the same
@param t the term to attempt to add
*/
public void addIfSamePower(Term t)
{
if (t.power == power)
{
coefficient += t.coefficient;
}
}
/**
Returns a string representation of the term with a ^ representing the exponent
@return a string representation of a term
*/
public String toString()
{
if (power == 0)
{
return Math.abs(coefficient) + "";
}
else if (power == 1)
{
return Math.abs(coefficient) + "x";
}
else
{
return Math.abs(coefficient) + "x^" + power;
}
}
}
Explanation / Answer
public class Polynomial {
private int[] coef; // coefficients p(x) = sum { coef[i] * x^i }
private int deg; // degree of polynomial (0 for the zero polynomial)
// a * x^b
public Polynomial(int a, int b) {
coef = new int[b+1];
coef[b] = a;
deg = degree();
}
// return the degree of this polynomial (0 for the zero polynomial)
public int degree() {
int d = 0;
for (int i = 0; i < coef.length; i++)
if (coef[i] != 0) d = i;
return d;
}
// return c = a + b
public Polynomial plus(Polynomial b) {
Polynomial a = this;
Polynomial c = new Polynomial(0, Math.max(a.deg, b.deg));
for (int i = 0; i <= a.deg; i++) c.coef[i] += a.coef[i];
for (int i = 0; i <= b.deg; i++) c.coef[i] += b.coef[i];
c.deg = c.degree();
return c;
}
// return (a - b)
public Polynomial minus(Polynomial b) {
Polynomial a = this;
Polynomial c = new Polynomial(0, Math.max(a.deg, b.deg));
for (int i = 0; i <= a.deg; i++) c.coef[i] += a.coef[i];
for (int i = 0; i <= b.deg; i++) c.coef[i] -= b.coef[i];
c.deg = c.degree();
return c;
}
// return (a * b)
// takes quadratic time (faster algorithms, e.g., via FFT are known)
public Polynomial times(Polynomial b) {
Polynomial a = this;
Polynomial c = new Polynomial(0, a.deg + b.deg);
for (int i = 0; i <= a.deg; i++)
for (int j = 0; j <= b.deg; j++)
c.coef[i+j] += (a.coef[i] * b.coef[j]);
c.deg = c.degree();
return c;
}
// return a(b(x)) - compute using Horner's method
public Polynomial compose(Polynomial b) {
Polynomial a = this;
Polynomial c = new Polynomial(0, 0);
for (int i = a.deg; i >= 0; i--) {
Polynomial term = new Polynomial(a.coef[i], 0);
c = term.plus(b.times(c));
}
return c;
}
// do a and b represent the same polynomial?
public boolean eq(Polynomial b) {
Polynomial a = this;
if (a.deg != b.deg) return false;
for (int i = a.deg; i >= 0; i--)
if (a.coef[i] != b.coef[i]) return false;
return true;
}
// use Horner's method to compute and return the polynomial evaluated at x
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;
}
// convert to string representation
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;
}
// test client
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);
StdOut.println("zero(x) = " + zero);
StdOut.println("p(x) = " + p);
StdOut.println("q(x) = " + q);
StdOut.println("p(x) + q(x) = " + r);
StdOut.println("p(x) * q(x) = " + s);
StdOut.println("p(q(x)) = " + t);
StdOut.println("0 - p(x) = " + zero.minus(p));
StdOut.println("p(3) = " + p.evaluate(3));
StdOut.println("p'(x) = " + p.differentiate());
StdOut.println("p''(x) = " + p.differentiate().differentiate());
}
}
-------------------
package polynomial;
import java.io.*;
import java.util.StringTokenizer;
/**
* This class implements a term of a polynomial.
*
* @author runb-cs112
*
*/
class Term {
/**
* Coefficient of term.
*/
public float coeff;
/**
* Degree of term.
*/
public int degree;
/**
* Initializes an instance with given coefficient and degree.
*
* @param coeff
* Coefficient
* @param degree
* Degree
*/
public Term(float coeff, int degree) {
this.coeff = coeff;
this.degree = degree;
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#equals(java.lang.Object)
*/
public boolean equals(Object other) {
return other != null && other instanceof Term
&& coeff == ((Term) other).coeff
&& degree == ((Term) other).degree;
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
public String toString() {
if (degree == 0) {
return coeff + "";
} else if (degree == 1) {
return coeff + "x";
} else {
return coeff + "x^" + degree;
}
}
}
/**
* This class implements a linked list node that contains a Term instance.
*
* @author runb-cs112
*
*/
class Node {
/**
* Term instance.
*/
Term term;
/**
* Next node in linked list.
*/
Node next;
/**
* Initializes this node with a term with given coefficient and degree,
* pointing to the given next node.
*
* @param coeff
* Coefficient of term
* @param degree
* Degree of term
* @param next
* Next node
*/
public Node(float coeff, int degree, Node next) {
term = new Term(coeff, degree);
this.next = next;
}
}
/**
* This class implements a polynomial.
*
* @author runb-cs112
*
*/
public class Polynomial {
/**
* Pointer to the front of the linked list that stores the polynomial.
*/
Node poly;
/**
* Initializes this polynomial to empty, i.e. there are no terms.
*
*/
public Polynomial() {
poly = null;
}
/**
* Reads a polynomial from an input stream (file or keyboard). The storage
* format of the polynomial is:
*
* <pre>
* <coeff> <degree>
* <coeff> <degree>
* ...
* <coeff> <degree>
* </pre>
*
* with the guarantee that degrees will be in descending order. For example:
*
* <pre>
* 4 5
* -2 3
* 2 1
* 3 0
* </pre>
*
* which represents the polynomial:
*
* <pre>
* 4 * x ˆ 5 - 2 * x ˆ 3 + 2 * x + 3
* </pre>
*
* @param br
* BufferedReader from which a polynomial is to be read
* @throws IOException
* If there is any input error in reading the polynomial
*/
public Polynomial(BufferedReader br) throws IOException {
String line;
StringTokenizer tokenizer;
float coeff;
int degree;
poly = null;
while ((line = br.readLine()) != null) {
tokenizer = new StringTokenizer(line);
coeff = Float.parseFloat(tokenizer.nextToken());
degree = Integer.parseInt(tokenizer.nextToken());
poly = new Node(coeff, degree, poly);
}
}
/**
* Returns the polynomial obtained by adding the given polynomial p to this
* polynomial - DOES NOT change this polynomial
*
* @param p
* Polynomial to be added
* @return A new polynomial which is the sum of this polynomial and p.
*/
public Polynomial add(Polynomial p) {
/*
* What's up.
*
* This code makes sure you didn't give me crap.
*
* GIGO, right?
*/
if (p.poly == null) {
return this;
} else if (this.poly == null) {
return p;
} else {
Polynomial retPol = new Polynomial();
retPol.poly = new Node(0, 0, null);
Node front = retPol.poly;
Node entered = p.poly; // this is the input
Node thisPol = this.poly; // this is from this structure
/*
* The code below does the actual addition
* by simultaneously looping through two
* polynomials.
*
* It's not the best way, it doesn't sort.
* But it works.
*
*/
while (entered != null || thisPol != null) {
boolean bothExist = (entered != null & thisPol != null);
boolean bothEqual = false;
if (bothExist) {
bothEqual = (entered.term.degree == thisPol.term.degree);
}
if (bothExist && bothEqual) {
retPol.poly.term = new Term(entered.term.coeff
+ thisPol.term.coeff, thisPol.term.degree);
thisPol = thisPol.next;
entered = entered.next;
} else {
if (entered != null && ((thisPol == null) || entered.term.degree < thisPol.term.degree)) {
retPol.poly.term = entered.term;
entered = entered.next;
} else {
retPol.poly.term = thisPol.term;
thisPol = thisPol.next;
}
}
retPol.poly.next = new Node(0, 0, null);
retPol.poly = retPol.poly.next;
}
/*
* This removes any zero entries, including the one my code adds in
* arbitrarily by default.
*
* Also, hello TA looking for arrays. Or Professor.
*
* There are no arrays here.
*/
Node previous = null;
Node current = front;
while (current != null) {
if (current.term.coeff == 0) {
current = current.next;
if (previous == null) {
previous = current;
} else {
previous.next = current;
}
} else {
previous = current;
current = current.next;
}
}
retPol.poly = front;
if (retPol.poly.term.coeff == 0 && retPol.poly.next.term.coeff == 0) {
Polynomial zero = new Polynomial();
zero.poly = new Node (0, 0, null);
return zero;
}
else
return retPol;
}
}
/**
* Returns the polynomial obtained by multiplying the given polynomial p
* with this polynomial - DOES NOT change this polynomial
*
* @param p
* Polynomial with which this polynomial is to be multiplied
* @return A new polynomial which is the product of this polynomial and p.
*/
public Polynomial multiply(Polynomial p) {
if (p.poly == null || this.poly == null) {
Polynomial zero = new Polynomial();
zero.poly = new Node (0, 0, null);
return zero;
} else {
Polynomial retPol = new Polynomial();
retPol.poly = new Node(0, 0, null);
Node front = retPol.poly;
Node entered = p.poly;
Node thisPol = this.poly;
int heighestMultiple = 0;
int lowestMultiple = 99999999;
while (entered != null) {
thisPol = this.poly;
while (thisPol != null) {
if (thisPol.term.degree + entered.term.degree > heighestMultiple)
heighestMultiple = thisPol.term.degree + entered.term.degree;
if (thisPol.term.degree + entered.term.degree < lowestMultiple)
lowestMultiple = thisPol.term.degree + entered.term.degree;
thisPol = thisPol.next;
}
entered = entered.next;
}
entered = p.poly;
Node create = front;
for (int i = lowestMultiple; i <= heighestMultiple; i++) {
create.term.degree = i;
create.term.coeff = 0;
create.next = new Node (0, 0, null);
create = create.next;
}
entered = p.poly;
while (entered != null) {
thisPol = this.poly;
while (thisPol != null) {
int degree = entered.term.degree + thisPol.term.degree;
create = front;
while (create != null) {
if (create.term.degree == degree) {
create.term.coeff = entered.term.coeff * thisPol.term.coeff;
}
create = create.next;
}
thisPol = thisPol.next;
}
entered = entered.next;
}
create = front;
while (create != null) {
if (create.term.degree == heighestMultiple) {
create.next = null;
create = create.next;
}
else
create = create.next;
}
retPol.poly = front;
return retPol;
}
}
/**
* Evaluates this polynomial at the given value of x
*
* @param x
* Value at which this polynomial is to be evaluated
* @return Value of this polynomial at x
*/
public float evaluate(float x) {
float retVal = 0;
Node currentMonomial = this.poly;
while (currentMonomial != null) {
float currentValue = (float) Math.pow(x,
currentMonomial.term.degree);
currentValue *= currentMonomial.term.coeff;
retVal += currentValue;
currentMonomial = currentMonomial.next;
}
return retVal;
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
public String toString() {
String retval;
if (poly == null) {
return "0";
} else {
retval = poly.term.toString();
for (Node current = poly.next; current != null; current = current.next) {
retval = current.term.toString() + " + " + retval;
}
return retval;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.