编码多项式除法

Question

我正在尝试为一项学校作业编写多项式的四个基本运算符。我目前停留在部门部分。维基百科有一个 pseudo code 的模型，但我无法真正将其正确地实现到我的代码中。部分作业还使用了 LinkedList，因此我的每个多项式都是一个 LinkedList，其中包含包含系数和指数变量的 Term 对象。

这是我目前的情况：

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();
    }
}

我试图按照维基百科的伪代码进行操作，但显然我没有完成它。任何帮助将不胜感激:)

Answer 1

严格遵循 pseudo-code，您会看到它接受两个多项式，returns 接受一个新多项式。这可能与您的其他运营商不一致，但可能是这里的最佳选择。所以你的方法 header 应该更符合

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

其中QRPair是由两个多项式组成的class；一个 quotient 和一个 remainder.

以下是伪代码的粗略翻译

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);
}

请注意，您仍然需要实施 deepCopy。我们不能执行赋值 r = a 的原因是因为这意味着 r 和 a 将引用相同的 object，这是我们不想要的。类似地，如果我们做 r = (LinkedList<Term>)a.clone()，那么 r 将有链表 a 的（浅）副本。但是，r 中的每个元素将引用与 a 中的每个元素相同的 object，这也不是我们想要的。我们希望 r 中的元素独立于 a.

中的元素

编码多项式除法

Coding Polynomial Division

java

linked-list

polynomial-math