c++ - 多项式乘法递归

Question

这是我的代码，为什么显示分段错误？有人可以纠正我的 mult4 函数...我知道问题是 mult4 并且我不确定函数 mult4 是否是多项式递归乘法的正确解决方案...

#include <iostream>
#include <cstdlib>    
using namespace std;

class Polynomial
{
    public:
        Polynomial()
        {
            deg=0;
            coeff = new float[deg+1];
            coeff[0]=0;
        }
        Polynomial(int n)
        {
            deg = n; 
            coeff = new float[deg+1];
            for(int i = 0; i<=deg;i++) 
                coeff[i] = rand()/(float)RAND_MAX;   
        }
        Polynomial(float *array, int n)
        {       
               deg=n;
               coeff=array;
        }
        Polynomial(const Polynomial& P)
        {
             deg = P.deg;
             coeff = new float[deg+1];

             for(int i=0;i<=deg;i++) coeff[i] = P.coeff[i];
        }
        ~Polynomial()
        {
            delete []coeff;   
        }

        Polynomial operator+(const Polynomial& P) const;
        Polynomial operator-(const Polynomial& P) const
        {
              int i;
                Polynomial c;
                 if(deg>=P.deg)
                 { 
                     c.deg=deg;
                     for(i=deg;i>=0;i--)
                      c.coeff[i]=coeff[i];
                     for(i=P.deg;i>=0;i--)
                 c.coeff[i]=c.coeff[i]-P.coeff[i];  
                 }
             else
                 {
                        c.deg=P.deg;
                        for(i=P.deg;i>=0;i--)
                        c.coeff[i]=-P.coeff[i];
                        for(i=deg;i>=0;i--)
                        c.coeff[i]=c.coeff[i]+coeff[i];  
     }

    return c;

        }
        Polynomial& operator=(const Polynomial& P)
        {
            if (this!=&P)
            {         
                delete [] coeff;
                deg = P.deg;
                coeff = new float[deg+1];

                for(int i=deg;i>=0;i--) coeff[i] = P.coeff[i];
            }

             return (*this);

        }


        float operator[](float x) // evaluation of polynomial
        {
            float rez=0;
            for(int i=deg;i>=0;i--)
                rez=rez*x+coeff[i];

            return rez;    
        }

        int degree() const
        {
            return deg;   
        }

    public:
        float *coeff; // array- representation of polynomial
        int deg;  //degree of polynomial

    friend ostream& operator<<(ostream &out, const Polynomial& P) //overload operatpr<<
    {
        for ( int i =P.deg; i >= 0; i-- ) 
        {
                     out << P.coeff[i] << "x^" << i << " ";
                     if(i>=1)
                     {
                        if(P.coeff[i-1]>0) out<<"+";
                     }
        }
    out << endl;
    return out;
    }   

};

Polynomial Polynomial::operator+(const Polynomial& P) const
{
    int i;
    Polynomial c;
   if(deg>=P.deg)
    { 
        c.deg=deg;
        for(i=deg;i>=0;i--)
            c.coeff[i]=coeff[i];
        for(i=P.deg;i>=0;i--)
          c.coeff[i]=c.coeff[i]+P.coeff[i];  
    }
    else
    {
         c.deg=P.deg;
        for(i=P.deg;i>=0;i--)
         c.coeff[i]=P.coeff[i];
        for(i=deg;i>=0;i--)
          c.coeff[i]=c.coeff[i]+coeff[i];  
     }

    return c;

}

Polynomial shift(Polynomial A, int x) 
{
  Polynomial c(A.deg+x);
    int k=0;

    for(int i=c.deg;i>=0;i--)
        c.coeff[i]=0;
   for(int i=A.deg;i>=0;i--)
   {
     c.coeff[c.deg-k]=A.coeff[i];
       k++;
   }
    return c;
}

Polynomial mult4( Polynomial P, Polynomial Q) 
{
    if(P.deg==1)
    {
      Polynomial qw(2);
            qw.coeff[0]=P.coeff[0]*Q.coeff[0];
            qw.coeff[2]=P.coeff[1]*Q.coeff[1];
            qw.coeff[1]=P.coeff[1]*Q.coeff[0]+Q.coeff[1]*P.coeff[0];
      return qw;
    }
 else
 {
    Polynomial p1(((P.deg)/2)-1);
    Polynomial p2(P.deg-(P.deg)/2);
    Polynomial q1(((Q.deg)/2)-1);
    Polynomial q2(Q.deg-(Q.deg)/2);

     int k=0;

    for(int i=p1.deg;i>=0;i--)
    {
        p1.coeff[i]=P.coeff[i];
    }
    for(int i=p2.deg;i>=0;i--)
    {    

        p2.coeff[i]=P.coeff[P.deg-k];
        k++;
    }
    for(int i=q1.deg;i>=0;i--)
    {
        q1.coeff[i]=Q.coeff[i];
    }
    k=0;
    for(int i=q2.deg;i>=0;i--)
    {    

        q2.coeff[i]=Q.coeff[P.deg-k];
        k++;
    }
      Polynomial t1,t2,t3;
     t1=mult4(p1+p2,q1+q2);
     t2=mult4(p1,q1);
     t3=mult4(p2,q2);

     return(t2+shift(t1-t2-t3,P.deg/2)+shift(t3,2*(P.deg/2)));
 }
}
int main()
{
    float *p=new float[4];
    for(int i=3;i>=0;i--)
        p[i]=-1.1+i;
    float *k=new float[5];
    for(int i=4;i>=0;i--)
        k[i]=-1.2+i;
    Polynomial P(p,3);
    Polynomial K(k,4);

    cout<<mult4(P,K);

    return 0;
}

score 0 · Accepted Answer

You have several errors in your code.

You need a copy constructor. Familiarize yourself with The Rule Of Three.

There are many lines where you set the deg of a Polynomial but don't allocate memory for coeff. For example, in shift, you have:

Polynomial shift(Polynomial A, float x)
{
   Polynomial c;
   int k=0;
   c.deg=A.deg+x;
   for(int i=c.deg;i>=0;i--)
      c.coeff[i]=0;

What you need is:

Polynomial shift(Polynomial A, float x)
{
   // Polynomial c(A.deg+x);
   // Not sure why you whether c.deg should be A.deg+x or just A.deg.
   Polynomial c(A.deg);
   int k=0;
   for(int i=c.deg;i>=0;i--)
      c.coeff[i]=0;

In the operator= function, you are changing the index incorrectly. In stead of using:

        for(int i=deg;i>=0;i++) coeff[i] = P.coeff[i];

you need to use:

        for(int i=deg;i>=0;i--) coeff[i] = P.coeff[i];
                         // ^^ Decrement, not increment

In mult4, your use of
```
p1.deg=((P.deg)/2)-1;
```
seems flawed. What happens when P.deg/2 is equal to 0? Perhaps you need to use:
```
p1.deg=(P.deg)/2;
```
Setting of q1.deg must be similarly updated.

I might have missed other errors.

c++ - 多项式乘法递归

1 回答 1

Related

Reference