C++ 多项式加法

Question

我试图在 C++ 中添加两个多项式，但我不知道从哪里开始。因此用户可以输入多项式的值，它们不需要按顺序或其他任何东西。

例如可以是:多边形 1:2x^5 + 5x^2 - 2x + 9保利 2: x^2 + 0

我将系数和指数存储在类(对象)私有(private)字段中。那么我是否会查看 Poly 1 中的第一个指数，首先在 Poly 2 中搜索相同的指数，如果找到则添加它们？然后继续第二学期？

请求的代码:(注意:目前的实现是错误的，我需要有关如何解决此问题的帮助。)

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

class polynomial
{
public:
polynomial();
polynomial(int);
polynomial(int exponent[], int coefficient[], int);
~polynomial();
polynomial &operator = (const polynomial &obj);
int evaluate(double uservalue);
polynomial operator+(const polynomial &obj) const;
void operator-(const polynomial &obj) const;
void operator*(const polynomial &obj) const;
friend istream & operator>> (istream & in, polynomial &obj);
friend ostream & operator<< (ostream & out, const polynomial &obj);
friend void growone(polynomial &obj);
private:
int *coefficient;
int *exponent;
int size;
};

和实现

polynomial polynomial::operator+(const polynomial &obj) const
{
    bool matchFound = false;
    polynomial tmp;
    if (size >= obj.size) {
        for (int i = 0; i < size; i++) {
            if (i >= tmp.size) {
                growone(tmp);
            }
            for(int y = 0; i < obj.size; i++) {
                if (exponent[i] == obj.exponent[y]) {
                    tmp.coefficient[i] = (coefficient[i]+obj.coefficient[y]);
                    tmp.exponent[i] = exponent[i];
                    tmp.size++;
                    matchFound = true;
                }
            }
            if (matchFound == false) {
                tmp.coefficient[i] = coefficient[i];
                tmp.exponent[i] = exponent[i];
                tmp.size++;
            }
            matchFound = false;
        }
    } else {



    }
    return tmp;
}

Answer 1

您并没有真正充分利用 C++ 的强大功能。一个好的规则是，如果您将非智能指针用于任何东西，您应该退后一步并重新考虑。

Stack Overflow 上关于 C 的大量问题都与指针有关的问题绝非偶然:-)

我要补充的另一点是，实际上浪费少量内存来大大简化您的代码可能是值得的。也就是说，我的意思是不要尝试创建稀疏数组来保存您的项(系数指数对)。相反，允许每个表达式将每个项保持到其最大值，将未使用项的系数简单地设置为零。除非你有类似 4x<sup>99999999999999</sup> + 3 的表达，占用的额外内存量可能是值得的。

为此，我建议使用 std::vector对于仅从零指数开始的系数。指数实际上是由 vector 中的位置决定的。所以表达式 4x<sup>9</sup> - 17x<sup>3</sup> + 3将被存储为 vector :

{3, 0, 0, -17, 0, 0, 0, 0, 0, 4}
 0 <------- exponent -------> 9

这实际上使加减多项式的任务变得异常容易，因为系数都排列得很好。

---

因此，考虑到这一点，让我们介绍一个简化的类来展示它是如何完成的:

#include <iostream>
#include <vector>

using std::cout;
using std::vector;
using std::ostream;

class Polynomial {
public:
    Polynomial();
    Polynomial(size_t expon[], int coeff[], size_t sz);
    ~Polynomial();
    Polynomial &operator=(const Polynomial &poly);
    Polynomial operator+(const Polynomial &poly) const;
    friend ostream &operator<<(ostream &os, const Polynomial &poly);
private:
    std::vector<int> m_coeff;
};

默认构造函数(和析构函数)非常简单，我们只需确保初始化的多项式始终至少有一项:

Polynomial::Polynomial() { m_coeff.push_back(0); }
Polynomial::~Polynomial() {}

constructor-from-array 稍微复杂一些，因为我们希望尽早将用户的“随心所欲”格式转换为我们可以轻松使用的格式:

Polynomial::Polynomial(size_t expon[], int coeff[], size_t sz) {
    // Work out largest exponent and size vector accordingly.

    auto maxExpon = 0;
    for (size_t i = 0; i < sz; ++i) {
        if (expon[i] > maxExpon) {
            maxExpon = expon[i];
        }
    }
    m_coeff.resize(maxExpon + 1, 0);

    // Fill in coefficients.

    for (size_t i = 0; i < sz; ++i) {
        m_coeff[expon[i]] = coeff[i];
    }
}

现在您将明白为什么我们决定不使用稀疏数组并将零指数放在 vector 的开头。博特operator=和 operator+很简单，因为他们已经知道所有术语在哪里:

Polynomial &Polynomial::operator=(const Polynomial &poly) {
    if (this != &poly) {
        m_coeff.clear();
        for (int coeff: poly.m_coeff) {
            m_coeff.push_back(coeff);
        }
    }
    return *this;
}

Polynomial Polynomial::operator+(const Polynomial &poly) const {
    // Create sum with required size.

    size_t thisSize = this->m_coeff.size();
    size_t polySize = poly.m_coeff.size();

    Polynomial sum;
    if (thisSize > polySize) {
        sum.m_coeff.resize(thisSize, 0);
    } else {
        sum.m_coeff.resize(polySize, 0);
    }

    // Do the actual sum (ignoring terms beyond each limit).

    for (size_t idx = 0; idx < sum.m_coeff.size(); ++idx) {
        if (idx < thisSize) sum.m_coeff[idx] += this->m_coeff[idx];
        if (idx < polySize) sum.m_coeff[idx] += poly.m_coeff[idx];
    }

    return sum;
}

现在我们只需要用一个输出函数和一个小的测试主线来完成这个:

ostream &operator<< (ostream &os, const Polynomial &poly) {
    bool firstTerm = true;
    if (poly.m_coeff.size() == 1 && poly.m_coeff[0] == 0) {
        os << "0";
        return os;
    }

    for (size_t idx = poly.m_coeff.size(); idx > 0; --idx) {
        if (poly.m_coeff[idx - 1] != 0) {
            if (firstTerm) {
                os << poly.m_coeff[idx - 1];
            } else if (poly.m_coeff[idx - 1] == 1) {
                os << " + ";
                if (idx == 1) {
                    os << poly.m_coeff[idx - 1];
                }
            } else if (poly.m_coeff[idx - 1] == -1) {
                os << " - ";
            } else if (poly.m_coeff[idx - 1] < 0) {
                os << " - " << -poly.m_coeff[idx - 1];
            } else {
                os << " + " << poly.m_coeff[idx - 1];
            }
            if (idx > 1) {
                os << "x";
                if (idx > 2) {
                    os << "^" << idx - 1;
                }
            }
            firstTerm = false;
        }
    }
    return os;
}

int main() {
    int    c1[] = {1, 2, 3, 4, 5};
    size_t e1[] = {3, 1, 4, 0, 9};
    Polynomial p1(e1, c1, (size_t)5);
    cout << "Polynomial 1 is " << p1 << " (p1)\n";

    int    c2[] = {6, 7, 8};
    size_t e2[] = {3, 7, 9};
    Polynomial p2(e2, c2, (size_t)3);
    cout << "Polynomial 2 is " << p2 << " (p2)\n";

    Polynomial p3 = p1 + p2;
    cout << "Polynomial 3 is " << p3 << " (p3 = p1 = p2);
}

我稍微重新格式化以显示类似术语的输出显示了它的实际效果:

Polynomial 1 is   5x^9 +        3x^4 +  x^3 + 2x + 4
Polynomial 2 is   8x^9 + 7x^7 +        6x^3
                 ===================================
Polynomial 3 is  13x^9 + 7x^7 + 3x^4 + 7x^3 + 2x + 4