java - 链表的多项式乘法度数数学不正确

Question

我的乘法逻辑在某处不正确。看来我没有考虑到何时必须添加与两个多项式相乘的结果相同次数的项。

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 high = Integer.MIN_VALUE;
        int low = Integer.MAX_VALUE;

        while (entered != null) {
            thisPol = this.poly; 

            while (thisPol != null) {
                if (thisPol.term.degree + entered.term.degree > high)
                    high = thisPol.term.degree + entered.term.degree;
                if (thisPol.term.degree + entered.term.degree < low)
                    low = thisPol.term.degree + entered.term.degree;

                thisPol = thisPol.next;
            }

            entered = entered.next;
        }

        entered = p.poly;

        Node create = front;
        for (int i = low; i <= high; 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 == high) {
                create.next = null;
                create = create.next;
            }
            else
                create = create.next;
        }

        retPol.poly = front;

        return retPol;
    }
}

我应该得到的答案是:

32.0x^9 + 16.0x^8 + -16.0x^7 + -20.0x^6 + 52.0x^5 + 38.0x^4 + -6.0x^3 + -6.0x^2 + 9.0x + 27.0

但我实际上得到:

32.0x^9 + 16.0x^8 + -16.0x^7 + -8.0x^6 + 16.0x^5 + 24.0x^4 + 12.0x^3 + -6.0x^2 + -9.0x + 27.0

看来3级到6级的逻辑是错误的。我知道这是一个逻辑错误。我只是不知道如何解决。我还知道应该为那些不正确的度数添加哪些术语，但它看起来只是绕过了这一点，只显示一个。

任何提示将不胜感激。谢谢。

Answer 1

我认为你应该总结所有对，而不是在这里选择最后(或随机)对:

                if (create.term.degree == degree) {
                    create.term.coeff += entered.term.coeff * thisPol.term.coeff;
                }

[更新]经过我的更正后的代码非常适合我:

public class PolynomialTest {
    public static void main(String[] args) {
        // 4x^5 - 2x^3 + 2x + 3
        Polynomial p1 = new Polynomial(new Node(4.0, 5, new Node(-2.0, 3, new Node(2.0, 1, new Node(3.0, 0, null)))));
        // 8x^4 + 4x^3 - 3x + 9
        Polynomial p2 = new Polynomial(new Node(8.0, 4, new Node(4.0, 3, new Node(-3.0, 1, new Node(9.0, 0, null)))));
        Polynomial p3 = p1.multiply(p2);
        System.out.println(p3.toString());
    }
}

class Term {
    int degree;
    double coeff;
}

class Node {
    Term term;
    Node next;
    public Node(double coeff, int degree, Node next) {
        this.term = new Term();
        this.term.degree = degree;
        this.term.coeff = coeff;
        this.next = next;
    }
}

class Polynomial {
    private Node poly;

    public Polynomial() {}

    public Polynomial(Node poly) {
        this.poly = poly;
    }

    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 high = Integer.MIN_VALUE;
            int low = Integer.MAX_VALUE;

            while (entered != null) {
                thisPol = this.poly; 

                while (thisPol != null) {
                    if (thisPol.term.degree + entered.term.degree > high)
                        high = thisPol.term.degree + entered.term.degree;
                    if (thisPol.term.degree + entered.term.degree < low)
                        low = thisPol.term.degree + entered.term.degree;

                    thisPol = thisPol.next;
                }

                entered = entered.next;
            }

            entered = p.poly;

            Node create = front;
            for (int i = low; i <= high; 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 == high) {
                    create.next = null;
                    create = create.next;
                }
                else
                    create = create.next;
            }

            retPol.poly = front;

            return retPol;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node n = poly;
        while (n != null) {
            if (sb.length() > 0)
                sb.append(" + ");
            sb.append(n.term.coeff);
            if (n.term.degree > 0)
                sb.append("x");
            if (n.term.degree > 1)
                sb.append("^").append(n.term.degree);
            n = n.next;
        }
        return sb.toString();
    }
}

此代码打印的内容正是您所期望的:

27.0 + 9.0x + -6.0x^2 + -6.0x^3 + 38.0x^4 + 52.0x^5 + -20.0x^6 + -16.0x^7 + 16.0x^8 + 32.0x^9