Сложение и умножение полиномов в виде связанных списков

Мой код полностью напечатан и правильно организован (пока не включая комментарии), и я полностью застрял в выполнении сложения и умножения с двумя полиномами. Может кто-то указать мне верное направление?

//*****************************************************************************************************************
// Polynomial.java
// February 21st, 2016
//*****************************************************************************************************************

/* Assignment 3 for IT Data Structures Module 6
   Polynomials as linked lists; stores two
   polynomials as two separate linked lists
   made up of nodes and allows for addition
   and multiplication of the polynomials             
                                                */

import java.util.Scanner;

public class Polynomial                          
{

    private static class Node
    {
        private int coef;
        private int expo;
        public Node next;

        public Node(int c, int e, Node n)
        {
            coef = c;
            expo = e;
            next = n;
        }

        public int getCoef()
        {
            return coef;
        }

        public int getExpo()
        {
            return expo;
        }

        public Node getNext()
        {
            return next;
        }

        public void setNext(Node n)
        {
            next = n;
        }

    }

    private Node head = null;
    private Node tail = null;
    private int size = 0;

    public Polynomial()
    {
    }

    public int size()
    {
        return size;
    }

    public boolean isEmpty()
    {
        return size == 0;
    }

    public void addTerm(int c, int e)
    {
        Node newest = new Node(c, e, null);

        if( isEmpty() )
        {
            head = newest;
        }

        else
        {
            tail.setNext(newest);
        }

        tail = newest;
        size++;
    }

    public void print()
    {
        String poly = "";

        for(Node i = head; i != null; i = i.next)
        {
            if(i.coef > 0)
            {

                poly = poly + " + " + i.coef + "x^" + i.expo;
            }

            else if(i.coef < 0)
            {
                poly = poly + " - " + (-i.coef) + "x^" + i.expo;
            }
        }

        System.out.println(poly + "\n");
    }

    public Polynomial add(Polynomial b)
    {
        Polynomial a = this;
        Polynomial c = new Polynomial();
        Node x = a.head;
        Node y = b.head;

        while( x!= null || y != null)
        {
            Node t = null;
            if (x == null)
            {
                t = new Node(y.coef, y.expo, y.next);
            }

            else if (y == null)
            {
                t = new Node(x.coef, x.expo, x.next);
            }

            else if (x.expo > y. expo)
            {
                t = new Node(x.coef, x.expo, x.next);
            }

            else if (x.expo < y.expo)
            {
                t = new Node(y.coef, y.expo, y.next);
            }

            else
            {
                int coef = x.coef + y.coef;
                int expo = x.expo;
                Node next = y.next;

                x = x.next;
                y = y.next;

                if (coef == 0)
                {
                    continue;
                }

                t = new Node(coef, expo, next);
            }

            c.tail.next = t;
            c.tail = c.tail.next;

        }

        return c;
    }

    public Polynomial multiply(Polynomial b)
    {
        Polynomial a = this;
        Polynomial c = new Polynomial();

        for(Node x = a.head; x != null; x = x.next)
        {
            Polynomial temp = new Polynomial();

            for(Node y = b.head; y != null; y = y.next)
            {
                temp.tail.next = new Node(x.coef * y.coef, x.expo + y.expo, temp.tail.next);
                temp.tail = temp.tail.next;
            }

            c = c.add(temp);
        }

        return c;
    }


    public static void main(String args[])
    {

        Polynomial p = new Polynomial();

        System.out.println("NEW POLYNOMIAL p(x): What order will this polynomial be?");
        Scanner scan = new Scanner(System.in);
        int o = scan.nextInt();

        System.out.println("Enter values for the coefficient and exponent of the first term with each value followed the return key.");
        Scanner scan2 = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();

        p.addTerm(a, b);

        for (int i = 1; i < o; i++)
        {
            System.out.println("Enter values for the coefficient and exponent of the next term with each value followed by the return key.");
            int c = scan.nextInt();
            int d = scan.nextInt();

            p.addTerm(c, d);
        }

        System.out.println("p(x) => ");
        p.print();


        Polynomial q = new Polynomial();

        System.out.println("NEW POLYNOMIAL q(x): What order will this polynomial be?");
        Scanner scan3 = new Scanner(System.in);
        int o2 = scan.nextInt();

        System.out.println("Enter values for the coefficient and exponent of the first term with each value followed the return key.");
        Scanner scan4 = new Scanner(System.in);
        int e = scan.nextInt();
        int f = scan.nextInt();

        q.addTerm(e, f);

        for (int j = 1; j < o2; j++)
        {
            System.out.println("Enter values for the coefficient and exponent of the next term with each value followed by the return key.");
            int g = scan.nextInt();
            int h = scan.nextInt();

            q.addTerm(g, h);
        }

        System.out.println("q(x) => ");
        q.print();

        System.out.println("Would you like to add p(x) and q(x)? Type 'yes' or 'no'. ");
        Scanner scan5 = new Scanner(System.in);
        String option = scan.next();

        if( option.equals("yes") )
        {
            p.add(q);
            System.out.println("The sum of p(x) and q(x) is: ");
            p.add(q).print();
        }

        else if( option.equals("no") )
        {
            System.out.println("Would you like to multiply p(x) and q(x)? Type 'yes' or 'no'. ");
            Scanner scan6 = new Scanner(System.in);
            String option2 = scan.next();

            if( option2.equals("yes") )
            {
                p.multiply(q);
                System.out.println("The product of p(x) and q(x) is: ");
                p.multiply(q).print();
            }

            else
            {
                System.out.println("Program terminated.");
                System.exit(0);
            }
        }

        System.out.println("Program terminated.");
        System.exit(0);

    }


}

person Christopher Garrett Joiner    schedule 22.02.2016    source источник


Ответы (1)


При умножении многочленов вы умножаете все члены первого числа на все члены второго.

Пример:

(Ax^2 + Bx + C) * (Dx + E)

становится

ADx^3 + AEx^2 + BDx^2 + BEx + CDx + CE

Оттуда вы добавляете коэффициенты подобных терминов (когда показатели одинаковы). Продолжая пример:

ADx^3 + (AE + BD)x^2 + (BE + CD)x + CE

Поэтому, если бы я делал это, я бы сначала создал функцию для умножения, а затем вторую функцию для объединения похожих терминов.

После выполнения обоих действий у вас теперь есть новый многочлен в правильной форме.

person Chris    schedule 15.03.2016