c++ - 多项式类 : Polynomial Multiplication

Question

我有一个 Polynomial 类，它有一个 get_vect 成员函数，它将整数存储在一个 vector 中，该 vector 是多项式系数的表示。现在，我正在尝试使用 Multiply 非成员函数将两个多项式相乘，但是当涉及到 vector 的实际乘法时，我被卡住了。到目前为止，我所拥有的是如下所示:

Polynomial Multiply(const Polynomial & poly1, const Polynomial & poly2)
{
    vector<int> Poly1 = poly1.get_vect();
    vector<int> Poly2 = poly2.get_vect();
    vector<int> Poly3;

    if( Poly1.size() < Poly2.size() )
    {
        for(size_t i = 0 ; Poly2.size()-Poly1.size() ; ++i )
        {
            Poly2.push_back(0);
        }
    }
    else if( Poly1.size() > Poly2.size() )
    {
        for(size_t i = 0 ; Poly1.size()-Poly2.size() ; ++i )
        {
            Poly1.push_back(0);
        }
    }

    return Poly3;
}

我看到它必须遵循以下模式:

Answer 1

好的，如果我理解正确的话，你需要 Poly3成为vector<int>它保存由 Poly1 表示的多项式之间的多项式乘法产生的系数和 Poly2 .

此请求中默认所有三个多项式都是单个变量中的多项式，每个系数代表该变量递增幂前面的系数。 IE。那{ 4, 5, 6, 7 }对应于 4 + 5x + 6x² + 7x³。

如果是这样，那么实际的乘法根本不应该那么困难，只要您的多项式不是特别大。您需要的代码大致如下所示:

    Poly3.resize(Poly1.size() + Poly2.size() - 1, 0);  // Make the output big enough; init to 0

    for (size_t i = 0; i != Poly1.size(); i++)
        for (size_t j = 0; j != Poly2.size(); j++)
            Poly3[i+j] += Poly1[i] * Poly2[j];

现在 Poly3 中的结果应该是Poly1的产品和 Poly2 .

完全有可能我忘记了边缘条件；我会在这里查看评论以指出我在哪里做的。不过与此同时，我做了一些测试，结果似乎给出了正确的输出。

如果您有相当大的多项式，那么您可能需要查看数学库来处理乘法。但是对于大约 20 - 30 项以下的任何内容？除非您的代码非常依赖于此多项式评估，否则我怀疑这不会成为您的瓶颈。