我正在教我的自我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
这是我在现代C 中对此的看法。
请注意使用有效系数的额外优化 Zero
自我包含的样本: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";
}
您需要将多项式视为一对序列(系数,可变):
[(系数1,变量1),(系数2,变量2),(系数3,变量3),...]
正如您所描述的,您从左到右进行迭代,每当 variable 部分相同时,将两个相邻的对组合成一个(当然,这当然假设列表已经由<<变量 part!)。
现在,当此列表中有三个或多个元素共享其变量时会发生什么?好吧,然后继续结合它们。实际上,不需要递归或任何复杂的东西。
在迭代期间的任何时刻,您将当前对的变量部分与 actible part >最后见到的 part part 。如果它们是相同的,则将它们结合在一起,然后继续。如果下一对您得仍然具有与最后一个SEAK 的变量相同的变量零件,那么您再次将它们结合在一起。如果正确执行此操作,则不应剩下任何重复。
这是一个如何做到这一点的示例。它通过创建一个新的对列表,然后在输入列表中迭代,为输入列表的每个项目迭代,它决定是否将其与上次推到新列表的项目相结合,还是将新元素添加到新列表中:
#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;
}
,如果您需要&ndash,您可以轻松地再次进行模板。我将float
用于系数,而strings
用于变量部分。实际上,这只是一个代码示例,可以显示如何在没有递归或并行使用的许多迭代器的情况下轻松完成此操作。
哦,该代码是为C 11编写的。同样,这只是一个模型,可以针对C 03进行调整。