yitiaolong.txt

一条龙游戏

一条龙游戏”。在一个3×3的棋盘上，甲乙双方进行对弃，双方在棋盘上轮流放入棋子，如果一方的棋子成一直线(横、竖或斜线)，则该方赢。请编写该游戏程序实现人与机器的比赛。比赛结果有三种：输、赢或平。 
在编程过程中请首先分析比赛中怎样才能获胜，找出第一步走在什么位置就最可能赢。
提问者：gw1225 - 试用期 一级 
其他回答    共 1 条
#include <iostream> 
#include <vector> 
#include <set> 
#include <algorithm> 
#include<math.h>
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; 
}