当前位置： 文江博客话题详情

使用递归将多项式相加

发布于 2024-10-28 03:23:39 字数 4852 浏览 0 评论 0原文

我需要使用递归方法将两个多项式相加。 这是一项逾期作业（我想考试中也会有类似的事情）。 主类：

public class Polynomial {

    private Node poly;


    public Polynomial(){
    poly = new Node();
    }

    private Polynomial(Node node){
    poly = node;
    }
    public void addTerm(int coef, int exp){
    Term term = new Term(coef, exp);
    Node node = new Node(term, null);

    Node iterator = poly;

    //if the list is empty just add the node
    if (poly.next == null){
        System.out.println("poly.next is null. adding node to first pos.");
        poly.next = node;
        return;
    }

    //if list isn't empty find the appropriate spot for it
    while (iterator.next != null){
        System.out.println("iterator.next != null...");
        if (exp < iterator.next.data.exp){
        System.out.println("\texp < iterator.next.data.exp");
        node.next = iterator.next;
        iterator.next = node;
        return;
        }
        if (exp == iterator.next.data.exp){
        System.out.println("\texp == iterator.next.data.exp");
        iterator.next.data.coef += coef;
        return;
        }
        iterator = iterator.next;
    }

    //if we get to this point then the list isn't empty
    //and it doesn't fit inside the list, hence it must
    //be added to the end of the list
    System.out.println("list wasn't empty, didn't fit inside");
    iterator.next = node;
    return;
    }

    @Override
    public String toString(){
    Node iterator = poly;
    String out = "";

    if (poly.next == null){
        return out;
    }
    while(iterator.next != null){
        out += iterator.next.data.coef;
        out += "*x^";
        out += iterator.next.data.exp;
        out += " + ";
        iterator = iterator.next;
    }
    return out.substring(0, out.lastIndexOf('+'));
    }



    public Polynomial addPolynomial (Polynomial that){
    Polynomial ret = new Polynomial();

    Polynomial iterator = this;

    return addPolynomial(that, ret, iterator);
    }

    public Polynomial addPolynomial(Polynomial that, Polynomial ret, Polynomial iterator){
    if (iterator.poly.next == null){
        return new Polynomial(that.poly);
    }

    if (that.poly.next == null){
        return new Polynomial(iterator.poly);
    }

    if (iterator.poly.next.data.exp < that.poly.next.data.exp){
        ret.addTerm(iterator.poly.next.data.coef, iterator.poly.next.data.exp);
        iterator.poly = iterator.poly.next;
        return iterator.addPolynomial(that);
    }

    if (iterator.poly.next.data.exp == that.poly.next.data.exp){
        ret.addTerm(iterator.poly.next.data.coef + that.poly.next.data.coef, iterator.poly.next.data.exp);
        iterator.poly = iterator.poly.next;
        that.poly = that.poly.next;
        return iterator.addPolynomial(that);
    }

    if (iterator.poly.next.data.exp > that.poly.next.data.exp){
        ret.addTerm(that.poly.next.data.coef, that.poly.next.data.exp);
        that.poly = that.poly.next;
        return iterator.addPolynomial(that);
    }
    return ret;
    }

    /*
     * Term
     */
    private class Term implements Comparable{
    int coef;
    int exp;

    public int getCoef() {
        return coef;
    }

    public void setCoef(int coef) {
        this.coef = coef;
    }

    public int getExp() {
        return exp;
    }

    public void setExp(int exp) {
        this.exp = exp;
    }

    public Term(int coef, int exp) {
        this.coef = coef;
        this.exp = exp;
    }
    public int compareTo(Object rhs){
        Term that = (Term)rhs;
        return this.exp - that.exp;
    }
    }//end Term


    /*
     * Node
     */
    private class Node{
    Term data;
    Node next;

    public Term getData() {
        return data;
    }

    public void setData(Term data) {
        this.data = data;
        this.next = null;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Node() {
        this.data = null;
        this.next = null;
    }

    public Node(Term data, Node next) {
        this.data = data;
        this.next = next;
    }
    }//end Node




}

测试类：

public class Polynomials {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Polynomial p1 = new Polynomial();
        Polynomial p2 = new Polynomial();
        Polynomial p0 = new Polynomial();
        p1.addTerm(1, 2);
        p1.addTerm(1, 4);
        p1.addTerm(1, 6);
    p2.addTerm(1, 1);
    p2.addTerm(1, 3);
    p2.addTerm(1, 5);
    System.out.println("p1 = " + p1.toString());
    System.out.println("p2 = " + p2.toString());

    System.out.println("Adding p1 to p2...");
    p0 = p1.addPolynomial(p2);
    System.out.println(p0.toString());
    }
}
原文

I need to add two polynomials together using a recursive method.
This is for a past-due assignment (I imagine a similar thing will be on a test).
Main class:

public class Polynomial {

    private Node poly;


    public Polynomial(){
    poly = new Node();
    }

    private Polynomial(Node node){
    poly = node;
    }
    public void addTerm(int coef, int exp){
    Term term = new Term(coef, exp);
    Node node = new Node(term, null);

    Node iterator = poly;

    //if the list is empty just add the node
    if (poly.next == null){
        System.out.println("poly.next is null. adding node to first pos.");
        poly.next = node;
        return;
    }

    //if list isn't empty find the appropriate spot for it
    while (iterator.next != null){
        System.out.println("iterator.next != null...");
        if (exp < iterator.next.data.exp){
        System.out.println("\texp < iterator.next.data.exp");
        node.next = iterator.next;
        iterator.next = node;
        return;
        }
        if (exp == iterator.next.data.exp){
        System.out.println("\texp == iterator.next.data.exp");
        iterator.next.data.coef += coef;
        return;
        }
        iterator = iterator.next;
    }

    //if we get to this point then the list isn't empty
    //and it doesn't fit inside the list, hence it must
    //be added to the end of the list
    System.out.println("list wasn't empty, didn't fit inside");
    iterator.next = node;
    return;
    }

    @Override
    public String toString(){
    Node iterator = poly;
    String out = "";

    if (poly.next == null){
        return out;
    }
    while(iterator.next != null){
        out += iterator.next.data.coef;
        out += "*x^";
        out += iterator.next.data.exp;
        out += " + ";
        iterator = iterator.next;
    }
    return out.substring(0, out.lastIndexOf('+'));
    }



    public Polynomial addPolynomial (Polynomial that){
    Polynomial ret = new Polynomial();

    Polynomial iterator = this;

    return addPolynomial(that, ret, iterator);
    }

    public Polynomial addPolynomial(Polynomial that, Polynomial ret, Polynomial iterator){
    if (iterator.poly.next == null){
        return new Polynomial(that.poly);
    }

    if (that.poly.next == null){
        return new Polynomial(iterator.poly);
    }

    if (iterator.poly.next.data.exp < that.poly.next.data.exp){
        ret.addTerm(iterator.poly.next.data.coef, iterator.poly.next.data.exp);
        iterator.poly = iterator.poly.next;
        return iterator.addPolynomial(that);
    }

    if (iterator.poly.next.data.exp == that.poly.next.data.exp){
        ret.addTerm(iterator.poly.next.data.coef + that.poly.next.data.coef, iterator.poly.next.data.exp);
        iterator.poly = iterator.poly.next;
        that.poly = that.poly.next;
        return iterator.addPolynomial(that);
    }

    if (iterator.poly.next.data.exp > that.poly.next.data.exp){
        ret.addTerm(that.poly.next.data.coef, that.poly.next.data.exp);
        that.poly = that.poly.next;
        return iterator.addPolynomial(that);
    }
    return ret;
    }

    /*
     * Term
     */
    private class Term implements Comparable{
    int coef;
    int exp;

    public int getCoef() {
        return coef;
    }

    public void setCoef(int coef) {
        this.coef = coef;
    }

    public int getExp() {
        return exp;
    }

    public void setExp(int exp) {
        this.exp = exp;
    }

    public Term(int coef, int exp) {
        this.coef = coef;
        this.exp = exp;
    }
    public int compareTo(Object rhs){
        Term that = (Term)rhs;
        return this.exp - that.exp;
    }
    }//end Term


    /*
     * Node
     */
    private class Node{
    Term data;
    Node next;

    public Term getData() {
        return data;
    }

    public void setData(Term data) {
        this.data = data;
        this.next = null;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Node() {
        this.data = null;
        this.next = null;
    }

    public Node(Term data, Node next) {
        this.data = data;
        this.next = next;
    }
    }//end Node




}

Test Class:

public class Polynomials {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Polynomial p1 = new Polynomial();
        Polynomial p2 = new Polynomial();
        Polynomial p0 = new Polynomial();
        p1.addTerm(1, 2);
        p1.addTerm(1, 4);
        p1.addTerm(1, 6);
    p2.addTerm(1, 1);
    p2.addTerm(1, 3);
    p2.addTerm(1, 5);
    System.out.println("p1 = " + p1.toString());
    System.out.println("p2 = " + p2.toString());

    System.out.println("Adding p1 to p2...");
    p0 = p1.addPolynomial(p2);
    System.out.println(p0.toString());
    }
}

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（2）

萌化 2024-11-04 03:23:39

您考虑过这种做法吗？

public class Polynomial {
public static void main(String[] args) {
    Polynomial p1 = new Polynomial();
    Polynomial p2 = new Polynomial();
    Polynomial p0 = new Polynomial();
    p1.addTerm(1, 2);
    p1.addTerm(1, 4);
    p1.addTerm(1, 6);
    p2.addTerm(1, 1);
    p2.addTerm(2, 3);
    p2.addTerm(2, 2);
    p2.addTerm(1, 5);
    System.out.println("p1 = " + p1.toString());
    System.out.println("p2 = " + p2.toString());

    System.out.println("Adding p1 to p2...");
    p0 = p1.addPolynomial(p2);
    System.out.println(p0.toString());

    for(int i = 0;i < 100;i++) {
        p1 = new Polynomial();
        p2 = new Polynomial();
        for(int j = 0;j < 4;j++) {
            p1.addTerm((int) (10 * Math.random()) - 5,
                    (int) (4 * Math.random()));
            p2.addTerm((int) (10 * Math.random()) - 5,
                    (int) (4 * Math.random()));
        }
        p0 = p1.addPolynomial(p2);
        System.out.println(p1 + "\n" + p2 + "\n" + p0 + "\n");
    }
}



enum Comp {
    LT, EQ, GT
}


static Comp cmp(int a, int b) {
    return (a < b) ? Comp.LT : (a == b) ? Comp.EQ : Comp.GT;
}

private Term poly;


public Polynomial() {
    poly = null;
}


public void addTerm(int coef, int exp) {
    if (coef == 0) return;
    Term term = new Term(coef, exp,null);
    if (poly == null) {
        poly = term;
    } else {
        poly = poly.add(term);
    }
}


@Override
public String toString() {
    if (poly == null) return "0";

    StringBuilder buf = new StringBuilder();
    poly.writeTo(buf);
    return buf.toString();
}


public Polynomial addPolynomial(Polynomial that) {
    Polynomial ret = new Polynomial();
    if (poly != null) {
        ret.poly = new Term(poly);
        if (that.poly != null) {
            ret.poly = ret.poly.add(new Term(that.poly));
        }
    } else if (that.poly != null) {
        ret.poly = new Term(that.poly);
    }
    return ret;
}


private class Term {
    final int coef;

    final int exp;

    final Term next;


    Term(int coef, int exp, Term next) {
        this.coef = coef;
        this.exp = exp;
        this.next = next;
    }


    Term(Term copy) {
        this.coef = copy.coef;
        this.exp = copy.exp;
        if (copy.next == null) {
            this.next = null;
        } else {
            this.next = new Term(copy.next);
        }
    }


    Term add(Term other) {
        if (other == null) return this;

        switch (cmp(this.exp, other.exp)) {
        case LT: {
            Term n = other.add(this);
            return n;
        }
        case GT: {
            if (next == null) {
                return new Term(coef,exp,other);
            }

            return new Term(coef,exp,next.add(other));
        }
        default: {
            Term n = (next==null) ? other.next : next.add(other.next);
            int nc = coef+other.coef;
            return (nc!=0) ? new Term(nc,exp,n) : n;
        }
        }
    }


    public void writeTo(StringBuilder app) {
        if (coef != 1 || exp == 0) app.append(coef);
        if (exp == 1) {
            app.append("x");
        } else if (exp != 0) {
            app.append("x^").append(exp);
        }
        if (next != null) {
            app.append('+');
            next.writeTo(app);
        }
    }
}
}

Have you considered this way of doing it?

public class Polynomial {
public static void main(String[] args) {
    Polynomial p1 = new Polynomial();
    Polynomial p2 = new Polynomial();
    Polynomial p0 = new Polynomial();
    p1.addTerm(1, 2);
    p1.addTerm(1, 4);
    p1.addTerm(1, 6);
    p2.addTerm(1, 1);
    p2.addTerm(2, 3);
    p2.addTerm(2, 2);
    p2.addTerm(1, 5);
    System.out.println("p1 = " + p1.toString());
    System.out.println("p2 = " + p2.toString());

    System.out.println("Adding p1 to p2...");
    p0 = p1.addPolynomial(p2);
    System.out.println(p0.toString());

    for(int i = 0;i < 100;i++) {
        p1 = new Polynomial();
        p2 = new Polynomial();
        for(int j = 0;j < 4;j++) {
            p1.addTerm((int) (10 * Math.random()) - 5,
                    (int) (4 * Math.random()));
            p2.addTerm((int) (10 * Math.random()) - 5,
                    (int) (4 * Math.random()));
        }
        p0 = p1.addPolynomial(p2);
        System.out.println(p1 + "\n" + p2 + "\n" + p0 + "\n");
    }
}



enum Comp {
    LT, EQ, GT
}


static Comp cmp(int a, int b) {
    return (a < b) ? Comp.LT : (a == b) ? Comp.EQ : Comp.GT;
}

private Term poly;


public Polynomial() {
    poly = null;
}


public void addTerm(int coef, int exp) {
    if (coef == 0) return;
    Term term = new Term(coef, exp,null);
    if (poly == null) {
        poly = term;
    } else {
        poly = poly.add(term);
    }
}


@Override
public String toString() {
    if (poly == null) return "0";

    StringBuilder buf = new StringBuilder();
    poly.writeTo(buf);
    return buf.toString();
}


public Polynomial addPolynomial(Polynomial that) {
    Polynomial ret = new Polynomial();
    if (poly != null) {
        ret.poly = new Term(poly);
        if (that.poly != null) {
            ret.poly = ret.poly.add(new Term(that.poly));
        }
    } else if (that.poly != null) {
        ret.poly = new Term(that.poly);
    }
    return ret;
}


private class Term {
    final int coef;

    final int exp;

    final Term next;


    Term(int coef, int exp, Term next) {
        this.coef = coef;
        this.exp = exp;
        this.next = next;
    }


    Term(Term copy) {
        this.coef = copy.coef;
        this.exp = copy.exp;
        if (copy.next == null) {
            this.next = null;
        } else {
            this.next = new Term(copy.next);
        }
    }


    Term add(Term other) {
        if (other == null) return this;

        switch (cmp(this.exp, other.exp)) {
        case LT: {
            Term n = other.add(this);
            return n;
        }
        case GT: {
            if (next == null) {
                return new Term(coef,exp,other);
            }

            return new Term(coef,exp,next.add(other));
        }
        default: {
            Term n = (next==null) ? other.next : next.add(other.next);
            int nc = coef+other.coef;
            return (nc!=0) ? new Term(nc,exp,n) : n;
        }
        }
    }


    public void writeTo(StringBuilder app) {
        if (coef != 1 || exp == 0) app.append(coef);
        if (exp == 1) {
            app.append("x");
        } else if (exp != 0) {
            app.append("x^").append(exp);
        }
        if (next != null) {
            app.append('+');
            next.writeTo(app);
        }
    }
}
}
回复 原文
简单 2024-11-04 03:23:39

嗯，这肯定比必要的要复杂一些。

因此，您想将多项式添加到已有的多项式中，即：
4*x^2 + 4 到 5*x^4+x+5，结果是： 5*x^4+4*x^2+x+9

显然，只需使用数组，但对于链表来说也不是那么难，代码应该如下所示：

你有两个指针，一个指向我们想要添加值的多项式中的当前位置（term1），另一个指向我们想要的多项式添加（term2），两者都初始化为链表中的最低条目（我们假设根据指数排序）。

while term1 != NULL && term2 != NULL do:
   term1 > term2:
      add term2 to list
      term2 = term2.next()
   term2 > term1:
      term1 = term1.next()
   term1 = term2:
      add term2 to term1
      term1 = term1.next()
      term2 = term2.next()
while term1 == NULL && term2 != NULL:
   add term2
   term2 = term2.next()

您可以轻松地对其进行调整以创建一个新的多项式，而不是将一个多项式添加到另一个多项式上。

好的，更多关于如何将迭代解决方案转变为递归解决方案的细节：
当考虑递归时，你必须做的第一件事就是退出条件。

在这种情况下，如果你认为这很简单：只要 term2 不为 NULL，我们就开始工作，一旦 term2 为 NULL，我们就完成了。

下一步是考虑一个好的方法签名，这一次也很容易，因为我们只需要这两个项，所以您可以只使用两个迭代器：
void addTogether(迭代器 term1, 迭代器 term2); （假设您使用的接口类似于 ListIterator，因为您需要在 term1 之前的位置插入 - 有多种方法可以实现）

现在您只需摆脱 while 循环并替换它们使用递归调用（在其中区分不同的情况，执行必要的操作并再次调用）

Well that's certainly a bit more complex than necessary.

So you want to add a Polynomial to an already existing one, i.e.:
4*x^2 + 4 to 5*x^4+x+5, which results in: 5*x^4+4*x^2+x+9

You could obviously simplify the problem quite a bit by just using an array, but it's also not that hard with a linked list, the code should look something like this:

You have two pointers one pointing to the current position in the polynomial we want to add values (term1) and another one in the one we want to add (term2), both initialized to the lowest entry in the linked list (which we assume is sorted according to the exponent).

while term1 != NULL && term2 != NULL do:
   term1 > term2:
      add term2 to list
      term2 = term2.next()
   term2 > term1:
      term1 = term1.next()
   term1 = term2:
      add term2 to term1
      term1 = term1.next()
      term2 = term2.next()
while term1 == NULL && term2 != NULL:
   add term2
   term2 = term2.next()

You can easily adapt that to also create a new polynomial instead of adding one to the other.

Okay so a little bit more details on how to turn the iterative solution into a recursive one:
The first thing you always have to do when thinking about recursion is your exit condition.

In this case if you think about that's easy: We only do work as long as term2 is not NULL, as soon as term2 is NULL we're finished.

The next step is thinking about a good method signature and that's also quite easy this time, since we only need the two terms, so you can just use the two iterators:
void addTogether(Iterator term1, Iterator term2); (assuming you're using an interface that's similar to the ListIterator, since you need to insert at the position before term1 - there are several ways to implement that)

ANd now you've just got to get rid of the while loops and replace them with a recursive call (in which you distinguish the different cases, do the necessary action and call it again)

回复 原文
~没有更多了~

关于作者

焚却相思

暂无简介

0 文章
0 评论
22 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

1CH1MKgiKxn9p

文章 0 评论 0

ゞ记忆︶ㄣ

文章 0 评论 0

JackDx

文章 0 评论 0

信远

文章 0 评论 0

yaoduoduo1995

文章 0 评论 0

霞映澄塘

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文