gznq

ÈçºÎÀûÓÃCÓïÑÔÇóËæ»úÊýÀûÓüӼõ³Ë³ýµÈÓÚ24µÄº¯Êý±í´ïʽ

ÕâÖÖÌâĿûÓа취д³öËã·¨À´£¬¶ÔÓÚ³ÌÐòÀ´Ëµ£¬Ã»ÓÐËã·¨¾ÍûÓа취À´ÊµÏÖ£¬¶øÇÒ4¸öËæ»úÊýÊÇÓпÉÄÜËã²»³ö24À´µÄ¡£

×î¼Ñ´ð°¸ - ÓÉͶƱÕß2008-06-10 16:23:35Ñ¡³ö

#include
#include
#include
#include

using namespace std;

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

class CombinationIterator
{
vector 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::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& 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
class VectorCombinationIterator
{
vector mVector;
Index mCurrentM;
CombinationIterator mIter;
public:
VectorCombinationIterator()
{}
VectorCombinationIterator(const vector& 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, vector > operator* () const
{
const vector& current = *mIter;
pair< vector, vector > result;
for( vector::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 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::mPool( 1024*1024 );

vector getPossibleResult( const vector& left, const vector& right )
{

vector result;
for( vector::const_iterator liter = left.begin(); liter != left.end() ; ++liter )
for( vector::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 getPossibleResult( const vector& expItems )
{
if( expItems.size() == 1 )
return expItems;
vector result;
VectorCombinationIterator iter( expItems );
while( iter != VectorCombinationIterator() )
{
pair< vector, vector > p = *iter;
if( p.first.size() != 0 && p.second.size() != 0 )
{
vector items = getPossibleResult( getPossibleResult( p.first ),
getPossibleResult( p.second ) );
result.insert( result.end(), items.begin(), items.end() );
}
++iter;
}
return result;
}

vector getPossibleResult( const vector& numbers )
{
vector expItems;
for( vector::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<mValue;
}
else if( ( item->mOperator == '+' item->mOperator == '-' ) && ( oper == '*' oper == '/' ) )
{
cout<<"( ";
printExpression( item->mLeftChild, item->mOperator, true );
cout<<" ";
cout<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<mOperator;
cout<<" ";
printExpression( item->mRightChild, item->mOperator, false );
cout<<" )";
}
else
{
printExpression( item->mLeftChild, item->mOperator, true );
cout<<" ";
cout<mOperator;
cout<<" ";
printExpression( item->mRightChild, item->mOperator, false );
}

}

void printExpression( ExpressionItem* item )
{
if( item->mLeftChild != NULL )
{
printExpression( item->mLeftChild, item->mOperator, true );
cout<<" ";
cout<mOperator;
cout<<" ";
printExpression( item->mRightChild, item->mOperator, false );
}
else
cout<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 vn;
vn.push_back( i );
vn.push_back( j );
vn.push_back( k );
vn.push_back( l );
vector exps = getPossibleResult( vn );

for( int m = 0; m < exps.size(); ++m )
if( exps[ m ]->mValue >= 23.999 && exps[ m ]->mValue <= 24.001 )
{
cout< printExpression( exps[ m ] );
cout<<" = "<mValue< break;
}
// if( m == exps.siz
e() )
// cout< }

return 0;
}