5

我正在自学 C++。

我正在尝试组合多项式。为此，我 使用简单的值组合定义了简单的类Polynomial<T>：Term<T>和Coefficient<T>（也可能只是 ）。complex<T>我已经定义了所需的运算符重载。

多项式通过对其项进行排序来进行比较 ( std::sort)。

我正在努力combineLikeTerms()；调用此方法时，将首先调用另一个成员方法，该方法将对该术语向量进行排序。例如：

4x^3 + 5x^2 + 3x - 4

将是一个可能的结果排序向量。

问题：

我在这个向量上使用了两个迭代器，我试图合并相同顺序的相邻项。

假设我们排序后的初始向量是这样的：

4x^3 - 2x^3 + x^3 - 2x^2 + x ...

在函数完成其迭代后，临时堆栈向量将看起来像这样 2x^3 + x^3 - 2x^2 + x ...如果我们看起来仍然有类似的术语，这需要再次重构。

我该怎么做呢？我正在考虑使用递归。

// ------------------------------------------------------------------------- //
// setPolynomialByDegreeOfExponent()
// should be called before combineLikeTerms
template <class T>
void Polynomial<T>::setPolynomialByDegreeOfExponent()
{
    unsigned int uiIndex = _uiNumTerms - 1;
    if ( uiIndex < 1 )
    {
        return;
    }
    struct _CompareOperator_
    {
        bool operator() ( math::Term<T> a, Term<T> b )
        {
            return ( a.getDegreeOfTerm() > b.getDegreeOfTerm() );
        } // operator()
    };
    stable_sort( _vTerms.begin(), _vTerms.end(), _CompareOperator_() );
} // setPolynomialByDegreeOfExponent

// ------------------------------------------------------------------------- //
// addLikeTerms()
template <class T>
bool Polynomial<T>::addLikeTerms( const Term<T>& termA, const Term<T>& termB, Term<T>& result ) const
{
    if ( termA.termsAreAlike( termB ) )
    {
        result = termA + termB;
        return true;
    }
    return false;
} // addLikeTerms

// ------------------------------------------------------------------------- //
// combineLikeTerms()
template <class T>
void Polynomial<T>::combineLikeTerms()
{
    // First We Order Our Terms.
    setPolynomialByDegreeOfExponent();
    // Nothing To Do Then
    if ( _vTerms.size() == 1 )
    {
        return;
    }
    Term<T> result; // Temp Variable
    // No Need To Do The Work Below This If Statement This Is Simpler
    if ( _vTerms.size() == 2 )
    {
        if ( addLikeTerms( _vTerms.at(0), _vTerms.at(1) )
    {
        _vTerms.clear();
            _vTerms.push_back( result );
        }
        return;
    }
    // For 3 Ore More Terms
    std::vector<Term<T>> vTempTerms; // Temp storage
    std::vector<Term<T>>::iterator it = _vTerms.begin();
    std::vector<Term<T>>::iterator it2 = _vTerms.begin()+1;
    bool bFound = addLikeTerms( *it, *it2, result );

    while ( it2 != _vTerms.end() )
    {
        if ( bFound )
        {
            // Odd Case Last Three Elems
            if ( (it2 == (_vTerms.end()-2)) && (it2+1) == (_vTerms.end()-1)) )
            {
                vTempTerms.push_back( result );
                vTempTerms.push_back( _vTerms.back() );
                break;
            }
            // Even Case Last Two Elems
            else if ( (it2 == (_vTerms.end()-1)) && (it == (_vTerms.end()-2)) )
            {
                vTempTerms.push_back( result );
                break;
            }
            else
            {
                vTempTerms.push_back( result );
                it += 2;    // Increment by 2
                it2 += 2;          "
                bFound = addLikeTerms( *it, *it2, result );
            }
            }
                else {
                // Push Only First One
                vTempTerms.push_back( *it );
                it++;   // Increment By 1
                it2++;         "
                // Test Our Second Iterator
                if ( it2 == _vTerms.end() )
                {
                    vTempTerms.push_back( *(--it2) );  // same as using _vTerms.back()
                }
                else
                {
                    bFound = addLikeTerms( *it, *it2, result );
                }
            }
        }
        // Now That We Have Went Through Our Container, We Need To Update It
        _vTerms.clear();
        _vTerms = vTempTerms;
        // At This point our stack variable should contain all elements from above,
        // however this temp variable can still have like terms in it.
        // ??? Were do I call the recursion and how do I define the base case
        // to stop the execution of the recursion where the base case is a
        // sorted std::vector of Term<T> objects that no two terms that are alike...
        // I do know that the recursion has to happen after the above while loop
    } // combineLikeTerms

有人可以帮我找到下一步吗？我很高兴听到显示的代码中的任何错误/效率问题。我爱c++

4

2 回答 2

3

这是我对现代 C++ 的看法。

注意有效系数为零的删除项的额外优化

自包含样本： http: //liveworkspace.org/code/ee68769826a80d4c7dc314e9b792052b

更新：发布了这个http://ideone.com/aHuB8的 c++03 版本

#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>

template <typename T>
struct Term
{
    T coeff;
    int exponent;
};

template <typename T>
struct Poly
{
    typedef Term<T> term_t;
    std::vector<term_t> _terms;

    Poly(std::vector<term_t> terms) : _terms(terms) { }

    void combineLikeTerms()
    {
        if (_terms.empty())
            return;

        std::vector<term_t> result;

        std::sort(_terms.begin(), _terms.end(), 
                [] (term_t const& a, term_t const& b) { return a.exponent > b.exponent; });

        term_t accum = { T(), 0 };

        for(auto curr=_terms.begin(); curr!=_terms.end(); ++curr)
        {
            if (curr->exponent == accum.exponent)
                accum.coeff += curr->coeff;
            else
            {
                if (accum.coeff != 0)
                    result.push_back(accum);
                accum = *curr;
            }
        }        
        if (accum.coeff != 0)
            result.push_back(accum);

        std::swap(_terms, result); // only update if no exception
    }
};

int main()
{
    Poly<int> demo({ { 4, 1 }, { 6, 7 }, {-3, 1 }, { 5, 5 } });

    demo.combineLikeTerms();

    for (auto it = demo._terms.begin(); it!= demo._terms.end(); ++it)
        std::cout << (it->coeff>0? " +" : " ") << it->coeff << "x^" << it->exponent;

    std::cout << "\n";
}
于 2012-10-19T07:19:05.487 回答
1

您需要将多项式视为一系列对（系数，变量）：

[(co​​efficient1,variable1),(coefficient2,variable2),(coefficient3,variable3),...]

正如您所描述的，您从左到右遍历它，只要变量部分相同，就将两个相邻的对组合成一个（这当然假设列表已经按变量部分排序！）。

现在，当此列表中有三个或更多元素共享它们的变量时会发生什么？好吧，那就继续组合它们。真的不需要递归或任何复杂的东西。

在迭代过程中的任何时候，您都可以将当前对的可变部分与最后看到的可变部分结合起来。如果它们相同，则将它们组合并继续。如果您得到的下一对仍然具有与最后一次看到的相同的可变部分，那么您将它们再次组合起来。如果您正确执行此操作，则不应留下任何重复项。

这是一个如何执行此操作的示例。它的工作原理是创建一个新的对列表，然后遍历输入列表，对于输入列表的每个项目，它决定是否将其与最后推送到新列表的项目组合，或者通过向新列表添加新元素：

#include <utility>
#include <vector>
#include <iostream>

typedef std::vector<std::pair<float,std::string>> Polynomial;

Polynomial combine_like_terms(const Polynomial &poly)
{
  if (poly.empty())
    return poly;

  /* Here we store the new, cleaned-up polynomial: */
  Polynomial clean_poly;

  /* Now we iterate: */    
  auto it = begin(poly);
  clean_poly.push_back(*it);
  ++it;
  while (it != end(poly)) {
    if (clean_poly.back().second == it->second)
      clean_poly.back().first += it->first; // Like term found!
    else
      clean_poly.push_back(*it); // Sequence of like-terms ended!
    ++it;
  }
  return clean_poly;
}

int main()
{
  Polynomial polynomial {
    { 1.0 , "x^2" },
    { 1.4 , "x^3" },
    { 2.6 , "x^3" },
    { 0.2 , "x^3" },
    { 2.3 , "x" },
    { 0.7 , "x" }
  };

  Polynomial clean_polynomial = combine_like_terms(polynomial);
  for (auto term : clean_polynomial)
    std::cout << '(' << term.first << ',' << term.second << ")\n";
  std::cout.flush();

  return 0;
}

如果需要，您可以轻松地将其再次模板化——我用于float系数和strings变量部分。它实际上只是一个代码示例，展示了如何在没有递归或大量并行使用的迭代器的情况下轻松完成此操作。

哦，代码是为 C++11 编写的。同样，它只是一个模型，可以针对 C++03 进行调整。

于 2012-10-19T07:11:32.760 回答