用 C++ 简化多项式中的项

Question

我正在尝试编写一个函数来简化多项式中的项：

假设我们可以用一个双元整数数组表示每一项，第一个成员表示变量，第二个成员是系数。例如 4a 和 3b 可以分别用 (1, 4) 和 (2, 3) 表示。在这些示例中，我们根据字母顺序 (a:1, b:2, c:3, ...).

通过整数显示了变量 (a, b, ..)

因此，多项式可以表示为这些项的向量<-int*>。例如 4a+2b+10c 可以显示为 {(1,4), (2,2), (3,10)}。现在，目标是简化多项式。例如：

2a+3c-a+5t-3c = a+5t
我已经用 C++ 编写了一个代码来完成这项工作，但是对于大型多项式来说它非常慢。

void simplify (vector<int*> &p)
{
    vector<int*>:: iterator it1 = p.begin();
    vector<int*>:: iterator it2;
    while (it1!=p.end())
    {
        if ((*it1)[1]!=0) // if the coefficient is not equal to zero
        {
            it2 = it1+1;
            while (it2!=p.end())
            {
                if ((*it1)[0]==(*it2)[0]) //if the variables are similar
                {
                    (*it1)[1] += (*it2)[1];
                    (*it2)[1]=0; //set the coefficient equal to zero 
                }
                it2++;
            }
        }
        it1++;
    }
    it1 = p.begin();
    while (it1!=p.end()) //removing the terms with zero coefficient
    {
        if ((*it1)[1]==0)
            it1 = p.erase (it1);
        else
            it1++;  
    }
}

感谢所有能告诉我代码问题是什么以及如何提高代码速度的人。

Answer 1

我建议使用术语的结构使代码更具可读性：

struct Term
{
  int coefficient;
  char variable_name;
  int  exponent;
};

以上结构对多项式项建模比 {6,2} 容易得多。
您的代码变得更具可读性，这有助于减少缺陷注入。

多项式则变为：

typedef std::vector<Term> Polynomial;

换句话说，这表明多项式是项的容器（向量）。

该结构还允许您按变量名和降序系数（或指数）对容器进行排序。

编辑 1：术语输入
您可以为 Term 重载 operator>> 以输入一个术语：

struct Term
{
  // as above.
  friend std::istream& operator>>(std::istream& input, Term& t);
};
std::istream& operator>>(std::istream& input, Term& t)
{
  input >> t.coefficient;
  input >> t.variable_name;
  input >> t.exponent;
  return input;
}

这允许您通过以下方式构建多项式：

Polynomial p;
Term t;
while (input >> t)
{
  p.push_back(t);
}

在我看来，比您的设计和实现更简单，更不容易出错。

Answer 2

您当然可以在代码中更改一些内容。但由于您主要关心的是效率，我建议您首先采取的行动是使用不同的算法。

您当前的算法会检查每个元素的向量余数，寻找相同的符号并将找到的符号相加以获得最终系数。因此你的算法是；

for i in range(0, p.size()):
    for j in range(i+1, p.size()):
        // do the processing

您自己可能会注意到，此算法的复杂度为 O(N²)，这是您编写代码的主要原因效率低下。

作为替代方案，您可以迭代向量并将值放入 std::set。（假设 STL 不是 off-limits，考虑到您对 std::vector 的使用）下面是我的想法的粗略实现，基于您的代码。

void simplify (vector<int*> &p)
{
    vector<int*>::iterator it1 = p.begin();
    vector<int*>::iterator it2 = p.end();
    map<int, int> m;
    map<int, int>::iterator itMap1, itMap2;
    while (it1!=it2)
    {
        if(m.find((*it1)[0]) != m.end())
        {
            m[(*it1)[0]] += (*it1)[1];
        }
        else
        {
            m[(*it1)[0]] = (*it1)[1];
        }
        it1++;
    }
    itMap = m.begin();
    itMap2 = m.end();
    p.resize(m.size());
    it = p.begin();
    while (itMap!=itMap2)
    {
        (*it1)[0] = itMap->first;
        (*it1)[1] = itMap->second;
        itMap++;
        it++;
    }
}

上面的实现遍历了一次vector，复杂度为O(N)，N为vector的初始大小。每次迭代中进行的操作的复杂度为 O(logN)（由于 the implementation of std::map）导致整体复杂度为 O(NlogN)，比二次复杂度的初始算法好很多。

请注意，这只是基于您的代码的粗略初始实现，对于您的初始代码和我建议的版本还有其他可能的改进。一个示例是使用 struct 或 class 来包含与指针相反的每个术语，并使您的代码更具可读性和更紧凑。另一个可能的改进可能是使用 unordered_map 而不是 map.

用 C++ 简化多项式中的项

simplifying terms in a polynomial by c++

c++

iterator

traversal

vector