c++ - 重载 * 运算符以将两个多项式相乘

Question

这里是 C++ 的初学者。我特别需要帮助来弄清楚我的重载 * 运算符有什么问题，它应该乘以我创建的 Poly 类的两个多项式。我的其他重载运算符似乎工作正常。这是原始问题:

P(x) = 2x4 + 3x3 – 12x2 + x – 19 (4th order polynomial)
  or 
P(x) = 2x7 + 5x5 – 7x2 + x – 19 (7th order polynomial)

Where the coefficients for the first and second equations can be described by the following array of     integers

'Coeff1[  ] = {-19, 1, -12, 3, 2}'
'Coeff2[[ ] = {-19, 1, -7, 0, 0, 5, 0, 2}'

Design and code a polynomial class in C++ that has the following properties:

class Poly{
private:
int order;  //order of the polynomial
int *coeff; // pointer to array of coeff on the heap
        // size of coeff array predicated on (order + 1)
public:
Poly( );        //default constructor – order=0 & coeff[0] =1
Poly(int Order , int Default = 1) ;// creates  Nth order poly
                                                             // and inits all coeffs
Poly(int Order, int *Coeff);  //creates an Nth polynomial & inits 
 ~Poly( );      // destructor
   :::::::                     // copy constructor

//mutators  & accessors
void set( ){// Query user for coefficient values);
void set(int coeff[ ], int size);  // input coeffs via external coeff vector
int getOrder( )const;  // get order of polynomial
int * get( );         //returns pointer to coeff array

//overloaded operators
Poly operator+( const Poly &rhs);       // add two polynomials
Poly operator-( const Poly &rhs);       // subt two polynomials
Poly operator*( const int scale);       // scale a  polynomial
Poly operator*(const Poly &rhs);        // mult two polynomials
bool  operator==(const Poly &rhs);      // equality operator
const int & operator[ ](int I)const;       // return the Ith coefficient
int & operator[ ](int I);                   // return the Ith coefficient

int operator( )(int X);         // evaluate P(x) according 

Poly & operator=(const Poly & rhs);
friend ostream & operator<<(ostream & Out, const Poly &rhs);

//other member functions
};

Demonstrate the following operations for the following Polynomials:
P1(x) = 2x4 + 3x3 – 12x2 + x – 19 (4th order polynomial)
P2(x) = 2x7 + 7x5 – 6x2 + x – 19 (7th order polynomial)

//display the following results  for the polynomials defined above
o   P3 = P1 + P2;
o   P3 = P2 – P1;
o   P3 = P1*10;
o   P3 = 10*P1;
o   P3 = P1*P2;
o   bool flag  = (P1==P2);
o   P1[3] = P2[5];  // assign the 5th coefficient of P2 to 3rd coefficient of P1
o   int Z = P1(int  X = 5);   // evaluate  Polynomial for input X
 // suggest using Horner’s method


o   The displayed polynomial for P2 should be printed as follows
    2X^7 + 7X^5 – 6X^2 + 1X – 1

到目前为止，这是我的代码:

#include <iostream>
#include <cmath>

using namespace std;

class Poly
{
private:
int order;
int *coeff;

public:
Poly();
Poly(int Order, int Default=1);
Poly(int Order, int *Coeff);
Poly(const Poly &copy);
~Poly();

void set();                             //ask the user for the coefficient values
void set(int *Coeff, int size);            //put the coefficient values in a external coeff vector
int getOrder() const;               //gets the order of the polynomial
int* get() const;                             //returns pointer to coeff array

Poly operator +(const Poly &rhs);
Poly operator -(const Poly &rhs);
Poly operator *(const int scale);
Poly operator *(const Poly &rhs);


bool operator ==(const Poly &rhs);
const int & operator [](int access) const;
int & operator [](int access);
int operator ()(int X);
Poly & operator =(const Poly &rhs);

friend ostream & operator <<(ostream &Out, const Poly &rhs);
};

 int main()  {

 int coeff1[] = {-19,1,-12,3,2};
 int coeff2[] = {-19,1,-7,0,0,5,0,2};

 Poly P1(4,coeff1);
 Poly P2(7, coeff2);
 Poly P3;

 cout << "P1: " << P1 << endl;
 cout << "P2: " << P2 << endl;

 P3 = P1 * P2;
 cout << "P1 * P2: " << P3 << endl;

 return 0;
}


Poly::Poly() : order(0)
{
coeff = new int[1];
coeff[0] = 1;

}

Poly::Poly(int Order, int Default) : order(Order)
{
coeff = new int[order+1];

for (int i = 0; i < order+1; i++){
    coeff[i] = Default;
}

}

Poly::Poly(int Order, int *Coeff) : order(Order), coeff(Coeff)
{

}

Poly::Poly(const Poly & copy)
{
order = copy.getOrder();
coeff = new int[order+1];

for (int i = 0; i < order+1; i++){
    coeff[i] = copy.get()[i];
}
}

Poly::~Poly()
{
//if(coeff){
//delete [] coeff;
//}
}

void Poly::set()
{
cout << "Enter your coefficients:\n";

for (int i = 0; i < order+1; i++){
    cin >> coeff[i];
}
}

void Poly::set(int *Coeff, int size)
{
delete [] coeff;
coeff = new int[size];
order = size;

for (int i = 0; i < order+1; i++){
    coeff[i] = Coeff[i];
}
} 

int Poly::getOrder() const
{
return order;
}

int* Poly::get() const
{
return coeff;
}

Poly Poly::operator +(const Poly &rhs)
{
int length = max(order+1, rhs.getOrder()+1);
int *answer = new int[length];

for (int i = 0; i < length + 1; i++){
    answer[i] = coeff[i] + rhs.get()[i];

}

if (order > rhs.getOrder()){
    for (int i = order+1 - rhs.getOrder()+1 ; i < order+1; i++){
        answer[i] = coeff[i];
    }
}

else if (order < rhs.getOrder()){
    for (int i = rhs.getOrder()+1 - order+1; i < rhs.getOrder()+1; i++){
        answer[i] = rhs.get()[i];
    }
}

return Poly(length-1, answer);
}

Poly Poly::operator -(const Poly &rhs)
{
int length = max(order+1, rhs.getOrder()+1);
int *answer = new int[length];

for (int i = 0; i < order+1 && i < rhs.getOrder() + 1; i++){
    answer[i] = coeff[i] - rhs.get()[i];
}

if (order > rhs.getOrder()){
    for (int i = order+1-rhs.getOrder()+1; i < order+1; i++){
        answer[i] = coeff[i];
    }
}

else if (order < rhs.getOrder()){
    for (int i = rhs.getOrder()+1 - order+1; i < rhs.getOrder()+1; i++){
        answer[i] = 0 - rhs.get()[i];
    }
}

return Poly(length-1, answer);
}

Poly Poly::operator *(const int scale)
{
int *answer = new int[order+1];

for (int i = 0; i < order+1; i++){
    answer[i] = coeff[i] * scale;
}

return Poly(order, answer);
}

Poly Poly::operator *(const Poly &rhs)
{    
int *shorter = NULL;
int *longer  = NULL;
int s = 0;
int l = 0;

if(order < rhs.getOrder()){
    shorter = coeff;
    s       = order;
    longer  = rhs.coeff;
    l       = rhs.order;
} else {
    shorter = rhs.coeff;
    s       = rhs.order;
    longer  = coeff;
    l       = order;
}

Poly sum = Poly(l, longer) * shorter[0];
int *prod;
int nl;
for (int i = 1; i <= s; i++){
    nl = l + i;

    prod = new int[nl + 1];

    for(int j = 0; j < i; j++){
        prod[j] = 0;
    }

    for(int k = 0; k <= l; k++){
        prod[k+i] = shorter[i] * longer[k];
    }

    sum = sum + Poly(nl, prod);
}

return sum; 
}

bool Poly::operator ==(const Poly &rhs)
{
bool result;

if (order == rhs.order){
    result = true;

    for(int i = 0; i<order+1; i++){
        if (coeff[i] != rhs.get()[i]){
            result = false;
        }
    }

}else result = false;

return result;
}

const int& Poly::operator[](int access) const
{
return coeff[order + 1 - access];
}

int& Poly::operator [](int access)
{
return coeff[order + 1 - access];
}

int Poly::operator ()(int x)
{
int total = 0;
for(int i = 0; i < order + 1; i++){
    total += coeff[i] * pow(x, i);
}
return total;

}

Poly &Poly::operator =(const Poly &rhs)
{
order = rhs.getOrder();
coeff = rhs.get();
return *this;

}

ostream& operator <<(ostream & Out, const Poly &rhs)
{
Out << rhs.get()[rhs.getOrder()] << "x^" << rhs.getOrder();      //first

for (int i = rhs.getOrder()-1; i > 0; i--){
    if (rhs.get()[i] < 0 || rhs.get()[i] > 1) {

    if(rhs.get()[i] > 0){
    Out << " + ";
    }

    Out  << rhs.get()[i] << "x^" << i << " ";

    }else if (rhs.get()[i] == 1){
        Out << "+ x ";
    }else if (rhs.get()[i] == 1){
        Out << "- x";
    }

}
if (rhs.get()[rhs.getOrder() - rhs.getOrder()] > 0) {
    Out << " + " << rhs.get()[rhs.getOrder() - rhs.getOrder()];      //last

}else Out << rhs.get()[rhs.getOrder() - rhs.getOrder()];      //last


Out << endl;

return Out;
}

`

这是我当前的输出。我一直得到的答案是正确答案的一半，但我似乎无法得到前半部分。

P1: 2x^4 + 3x^3 -12x^2 + x -19

P2: 2x^7 + 5x^5 -7x^2 + x -19

P1 * P2: -114x^5 + 49x^4 -76x^3  + 362x^2 -38x^1  + 361

感谢任何帮助。谢谢

Answer 1

首先，停止手动管理内存。替换 order和 coeff与 std::vector<int> values; .这捆绑了 size()对于 order ，并为您处理内存管理。

如果你不知道如何使用std::vector然而，学习:这比学习如何编写自己的代码要容易得多 Poly类。

实现的下一步Poly * Poly是实现Poly& operator*=( Poly const& rhs );

最后一步是friend Poly operator*( Poly lhs, Poly const& rhs ) { return std::move(lhs*=rhs); }没有理由使用多条线，它可以是 inline .

剩下 operator*= .

实现*=的第一步它如此实现operator+(Poly const&, Poly const&) , 再次通过 Poly& operator+=(Poly const&) .添加很容易，我会把它留给你。

下一步是标量乘法。实现 Poly& operator*=(int) , 从它 friend Poly operator*(Poly lhs, int x) { return std::move( lhs*=x ); }和 friend Poly operator*(int x, Poly rhs) { return std::move( rhs*= x ); } .这称为“标量乘法”。

一旦我们有了这些，*=变得容易。

1. 存储初始值的拷贝。 ( Poly init = std::move(*this); )

2. 创建一个返回值(空)。

3. 对于右侧的每个系数，执行 retval += coeff * init;

4. return *this = std::move(retval);

这是解决方案的草图。要真正解决它，您需要在每个阶段实现测试。因为我实现了 *=在其他操作方面，测试每个操作以确保它们正常工作是获得可调试 *= 的关键。 .然后你测试*= , 然后你测试 * , 然后你就完成了。

如果您在兼容的 C++ 编译器中编译，使用 std::vector 是件好事是你的默认复制、移动、分配和移动分配操作做正确的事情，你的默认析构函数也是如此。寻求使用专门的资源管理类来管理资源，并遵循零法则，这样您的痛苦就会减少。

注意上面的*=并不比 * 容易写多少, 但总的来说 *=更容易，所以无论如何你都应该养成这个习惯。

最后，请注意，这会分配比所需更多的内存，并且不是最优的。然而，很容易得到正确的。在你实现了类似上面的东西之后，你可以通过多种方式使它更优化。您可以使用 karatsuba 乘法，您可以使用表达式模板来避免 result += coeff * init; 上的中间乘法线，你可以reserve result 中适当的空间量，或者您可以开始手动使用索引。

第一步应该是正确性，因为如果你有一个正确的算法，你至少可以用它来测试你更优化(更棘手)的算法。