obs吧:关于天津自考高级语言程序设计（一）的实践考核

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

typedef __int64 BigInteger;
typedef unsigned int Index;
typedef double Number;

class CombinationIterator
{
vector<Index> mCurrent;
Index mN;
Index mM;
static BigInteger factorial( Index n )
{
BigInteger fact = 1;
for( Index i = 2; i <= n; ++i )
fact *= i;
return fact;
}
public:
CombinationIterator(): mN( 0 ), mM( 0 )
{}
CombinationIterator( Index n, Index m )
: mN( n ), mM( m ),
mCurrent( (vector<Index>::size_type) m )
{
if( m > n || n < 1 || m < 1 )
throw 1;
for( Index i = 0; i < m; ++i )
mCurrent[ i ] = i;
}
void operator ++ ()
{
if( mM == 0 )
throw 1;
if( mCurrent[ 0 ] == mN - mM )
{
mN = mM = 0;
return;
}
Index i = mM - 1;
while( mCurrent[ i ] == mN - mM + i )
--i;
mCurrent[ i ] = mCurrent[ i ] + 1;
for( Index j = i + 1; j < mM; ++j )
mCurrent[ j ] = mCurrent[ i ] + j - i;
}
const vector<Index>& operator* () const
{
return mCurrent;
}
bool operator == ( const CombinationIterator& that ) const
{
if( mM == that.mM && mM == 0 )
return true;// both end
return mM == that.mM && mN == that.mN && mCurrent == that.mCurrent;
}
bool operator != ( const CombinationIterator& that ) const
{
return !( *this == that );
}
};

template<typename T>
class VectorCombinationIterator
{
vector<T> mVector;
Index mCurrentM;
CombinationIterator mIter;
public:
VectorCombinationIterator()
{}
VectorCombinationIterator(const vector<T>& v)
: mVector( v ), mCurrentM( 1 ), mIter( (Index) v.size(), mCurrentM )
{}
void operator ++ ()
{
++mIter;
if( mIter == CombinationIterator() && mCurrentM < mVector.size() )
{
++mCurrentM;
mIter = CombinationIterator( (Index) mVector.size(), mCurrentM );
}
}
pair< vector<T>, vector<T> > operator* () const
{
const vector<Index>& current = *mIter;
pair< vector<T>, vector<T> > result;
for( vector<T>::size_type i = 0; i < mVector.size(); ++i )
if( find( current.begin(), current.end(), i ) != current.end() )
result.first.push_back( mVector[i] );
else
result.second.push_back( mVector[i] );
return result;
}
bool operator == ( const VectorCombinationIterator& that ) const
{
if( mIter == that.mIter && mIter == CombinationIterator() )
return true;// both end
return mCurrentM == that.mCurrentM && mVector == that.mVector && mIter == that.mIter;
}
bool operator != ( const VectorCombinationIterator& that ) const
{
return !( *this == that );
}
};

static char gOperatorChars[]={'+','-','*','/'};

struct ExpressionItem
{
Number mValue;
char mOperator;
ExpressionItem* mLeftChild;
ExpressionItem* mRightChild;
ExpressionItem(){}
ExpressionItem( Number v, char oper, ExpressionItem* left, ExpressionItem* right )
: mValue( v ), mOperator( oper ), mLeftChild( left ), mRightChild( right )
{}
static vector<ExpressionItem> mPool;
static ExpressionItem* alloc( Number v, char oper, ExpressionItem* left, ExpressionItem* right )
{
mPool.push_back( ExpressionItem( v, oper, left, right ) );
return &*mPool.rbegin();
}
};

vector<ExpressionItem> ExpressionItem::mPool( 1024*1024 );

vector<ExpressionItem*> getPossibleResult( const vector<ExpressionItem*>& left, const vector<ExpressionItem*>& right )
{
vector<ExpressionItem*> result;
for( vector<ExpressionItem*>::const_iterator liter = left.begin(); liter != left.end() ; ++liter )
for( vector<ExpressionItem*>::const_iterator riter = right.begin(); riter != right.end() ; ++riter )
{
result.push_back( ExpressionItem::alloc( (*liter)->mValue + (*riter)->mValue, '+', *liter, *riter ) );
result.push_back( ExpressionItem::alloc( (*liter)->mValue - (*riter)->mValue, '-', *liter, *riter ) );
result.push_back( ExpressionItem::alloc( (*liter)->mValue * (*riter)->mValue, '*', *liter, *riter ) );
if( (*riter)->mValue != 0.0 )
result.push_back( ExpressionItem::alloc( (*liter)->mValue / (*riter)->mValue, '/', *liter, *riter ) );
}
return result;
}

vector<ExpressionItem*> getPossibleResult( const vector<ExpressionItem*>& expItems )
{
if( expItems.size() == 1 )
return expItems;
vector<ExpressionItem*> result;
VectorCombinationIterator<ExpressionItem*> iter( expItems );
while( iter != VectorCombinationIterator<ExpressionItem*>() )
{
pair< vector<ExpressionItem*>, vector<ExpressionItem*> > p = *iter;
if( p.first.size() != 0 && p.second.size() != 0 )
{
vector<ExpressionItem*> items = getPossibleResult( getPossibleResult( p.first ),
getPossibleResult( p.second ) );
result.insert( result.end(), items.begin(), items.end() );
}
++iter;
}
return result;
}

vector<ExpressionItem*> getPossibleResult( const vector<Number>& numbers )
{
vector<ExpressionItem*> expItems;
for( vector<Number>::const_iterator iter = numbers.begin(); iter != numbers.end(); ++iter )
expItems.push_back( ExpressionItem::alloc( *iter, 0, NULL, NULL ) );
return getPossibleResult( expItems );
}

void printExpression( ExpressionItem* item, char oper, bool isLeftChild )
{
if( item->mLeftChild == NULL )
{
cout<<item->mValue;
}
else if( ( item->mOperator == '+' || item->mOperator == '-' ) && ( oper == '*' || oper == '/' ) )
{
cout<<"( ";
printExpression( item->mLeftChild, item->mOperator, true );
cout<<" ";
cout<<item->mOperator;
cout<<" ";
printExpression( item->mRightChild, item->mOperator, false );
cout<<" )";
}
else if( !isLeftChild &&
( ( ( item->mOperator == '+' || item->mOperator == '-' ) && oper == '-' ) ||
( ( item->mOperator == '*' || item->mOperator == '/' ) && oper == '/' ) ) )
{
cout<<"( ";
printExpression( item->mLeftChild, item->mOperator, true );
cout<<" ";
cout<<item->mOperator;
cout<<" ";
printExpression( item->mRightChild, item->mOperator, false );
cout<<" )";
}
else
{
printExpression( item->mLeftChild, item->mOperator, true );
cout<<" ";
cout<<item->mOperator;
cout<<" ";
printExpression( item->mRightChild, item->mOperator, false );
}
}

void printExpression( ExpressionItem* item )
{
if( item->mLeftChild != NULL )
{
printExpression( item->mLeftChild, item->mOperator, true );
cout<<" ";
cout<<item->mOperator;
cout<<" ";
printExpression( item->mRightChild, item->mOperator, false );
}
else
cout<<item->mValue;
}

int main()
{
for( int i = 1; i <= 10; ++i )
for( int j = 1; j <= 10; ++j )
for( int k = 1; k <= 10; ++k )
for( int l = 1; l <= 10; ++l )
{
if( i > j || j > k || k > l )
continue;
ExpressionItem::mPool.clear();
ExpressionItem::mPool.reserve( 1024*1024 );
vector<Number> vn;
vn.push_back( i );
vn.push_back( j );
vn.push_back( k );
vn.push_back( l );
vector<ExpressionItem*> exps = getPossibleResult( vn );

for( int m = 0; m < exps.size(); ++m )
if( exps[ m ]->mValue >= 23.999 && exps[ m ]->mValue <= 24.001 )
{
cout<<i<<','<<j<<','<<k<<','<<l<<" \t---\t";
printExpression( exps[ m ] );
cout<<" = "<<exps[ m ]->mValue<<endl;
break;
}
// if( m == exps.size() )
// cout<<i<<','<<j<<','<<k<<','<<l<<" have no possible result"<<endl;
}

return 0;
}