Kylie Stamey - 6 months ago 58

Java Question

I'm trying to code the four basic operators for polynomials for a school assignment. I am currently stuck on the division portion. Wikipedia has a mock-up of the pseudo code but I can't really implement it into my code properly. Part of the assignment was also to use a LinkedList so each of my Polynomials is a LinkedList with Term objects containing a coefficient and exponent variable.

Here's what I have so far:

`public void dividePolynomials(LinkedList<Term> a, LinkedList<Term> b)`

{

LinkedList<Term> q = new LinkedList<Term>;

LinkedList<Term> r = a;

while(!isEmpty(r) && (r.highestDegree() > d.highestDegree()))

{

int co = r.get(0).getCo()/d.get(0).getCo();

int ex = r.get(0).getEx()/d.get(0).getEx();

Term t = new Term();

}

}

I tried to follow the Wikipedia pseudo code but obviously I didn't complete it. Any help would be much appreciated :)

Answer

Following strictly to the pseudo-code, you'll see that takes in two polynomials, and returns a new polynomial. This may not be consistent with your other operators, but is probably the best choice here. So your method header should be more along the lines of

`public QRPair dividePolynomials(LinkedList<Term> a, LinkedList<Term> b)`

where `QRPair`

is a class consisting of two polynomials; a `quotient`

and a `remainder`

.

The following is a rough translation of the pseudocode.

```
public LinkedList<Term> deepCopy(LinkedList<Term> p) {
//implement this!
}
public QRPair dividePolynomials(LinkedList<Term> a, LinkedList<Term> b) {
LinkedList<Term> q = "0" //set q to be the polynomial 0
LinkedList<Term> r = deepCopy(a); //want a copy of a, not just reference.
while(!isEmpty(r) && (r.highestDegree() > d.highestDegree()))
{
int co = r.get(0).getCo()/d.get(0).getCo();
int ex = r.get(0).getEx()/d.get(0).getEx();
Term t = new Term(co,ex);
q = addPolynomials(q,t);
r = subtractPolynomials(r,multiplyPolynomials(t,d));
//assume subtract/multiplyPolynomial returns LinkedList<Term>
}
return QRPair(q,r);
}
```

Note that you still have to implement `deepCopy`

. The reason why we can't do the assignment `r = a`

is because that means `r`

and `a`

would reference the same object, which we don't want. Similarly, if we do `r = (LinkedList<Term>)a.clone()`

, then `r`

would have a (shallow) copy of the linked list `a`

. However, each element in `r`

would reference the same object as each element in `a`

, which is also not what we want. We want elements in `r`

to be independent from elements of `a`

.

Source (Stackoverflow)