软讯网络 > 编程语言 > C/C++ > 交互式“算24”游戏
【标 题】：交互式“算24”游戏
【关键字】：
24
【来 源】：http://www.cublog.cn/u/22894/showart.php?id=166323
交互式“算24”游戏
//--------------------------------------------------------
// 交互式“算24”游戏：若干个数，通过 + - * 四则运算（包括括号），
// 求出等于目标数值的表达式。 提供人机交互操作，包含两种模式： 用户输入和随机生成。
//
// 算法： (引用 chai2010@linuxsir.org)
// 把输入的数据看做一个集合，集合中有n个元素。
// 从集合中任取2个元素分别进行+-*/运算，
// 把运算的结果替换n集合中取出的2个元素
// 现在集合中有(n-1)个元素
// 对含有(n-1)个元素的新集合递归进行上述判断
// 如果集合只剩下1个元素且该，则就是最终结果
//
// 实现： C++， vector， 递归
//
//--------------------------------------------------------
#include <iostream>
#include <sstream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
//参与“算24”的运算类型，最好是浮点数
typedef float data_t;
#define GET_EXPR(des,src) do{ \
if(src.expr.str().empty())
\
des.expr<<src.data; \
else des.expr<<src.expr.str();
\
}while(0)
class element{
friend element operator+(element &, element &);
friend element operator-(element &, element &);
friend element operator*(element &, element &);
friend element operator/(element &, element &);
friend void cal_target(vector<element> );
friend class NumberGame;
private:
data_t data;
ostringstream expr;
public:
element(data_t const& x):data(x){ }
~element(){ expr.str(""); data=0; }
element(element const& rhs):data(rhs.data){ expr<<rhs.expr.str(); }
element& operator=(element const&);
void show_expr() { cout<<expr.str(); }
void show_data() { cout<<data; }
};
element& element::operator=(element const& rhs)
{
if(this!=&rhs){
data=rhs.data;
expr.str("");
expr<<rhs.expr.str();
}
return *this;
}
element operator+(element& rhs1, element& rhs2)
{
element ret(rhs1.data+rhs2.data);
ret.expr<<"(";
GET_EXPR(ret,rhs1);
ret.expr<<"+";
GET_EXPR(ret,rhs2);
ret.expr<<")";
return ret;
}
element operator-(element & rhs1, element & rhs2)
{
element ret(rhs1.data-rhs2.data);
ret.expr<<"(";
GET_EXPR(ret,rhs1);
ret.expr<<"-";
GET_EXPR(ret,rhs2);
ret.expr<<")";
return ret;
}
element operator*(element& rhs1, element& rhs2)
{
element ret(rhs1.data*rhs2.data);
ret.expr<<"(";
GET_EXPR(ret,rhs1);
ret.expr<<"*";
GET_EXPR(ret,rhs2);
ret.expr<<")";
return ret;
}
element operator/(element& rhs1, element& rhs2)
{
if(rhs2.data){
element ret(rhs1.data/rhs2.data);
ret.expr<<"(";
GET_EXPR(ret,rhs1);
ret.expr<<"/";
GET_EXPR(ret,rhs2);
ret.expr<<")";
return ret;
}else{
cerr<<"divide by 0 error!"<<endl;
abort();
}
}
class NumberGame{
private:
vector<element> result;
vector<element> vin;
data_t target;
void init();
void cal_target(vector<element>);
void generate();
void show_puzzle();
void show_keypress();
void show_one_answer();
void show_all_answers();
public:
NumberGame(){}
~NumberGame(){ result.clear(); vin.clear(); }
bool input();
bool output();
bool random();
};
void NumberGame::init()
{
vin.clear();
result.clear();
}
bool NumberGame::input()
{
data_t e;
int count=0;
cout<<endl<<"How many numbers will you input( 0 to quit): ";
cin>>count;
if(count<1) return false;
if( count>8 ){
cout<<"Are you crazy? It may take a very long time to figure it out !"<<endl;
}
init();
for(int i=1;i<=count;i++){
cout<<"num"<<i<<": ";
cin>>e;
vin.push_back(e);
}
cout<<"Your TARGET number: ";
cin>>target;
cal_target(vin);
return true;
}
bool NumberGame::output()
{
show_all_answers();
return true;
}
void NumberGame::generate()
{
do{
init();
srand(time(NULL));
target=10+rand()%15;
int count=3+rand()%2;
for(int i=1; i<=count; i++){
vin.push_back( rand()%10 );
//delay();
}
cal_target(vin);
}while(result.empty());
}
void NumberGame::show_puzzle()
{
vector<element>::iterator it;
cout<<"----------------------"<<endl;
for(it=vin.begin(); it!=vin.end(); it++)
cout<<it->data<<" ";
cout<<" = "<<target<<" ?"<<endl<<"----------------------"<<endl;
}
void NumberGame::show_keypress()
{
cout<<"'a': get an answer; ";
cout<<"'A' all answers; ";
cout<<"'n' to next puzzle; ";
cout<<"'q' to quit."<<endl;
}
void NumberGame::show_one_answer()
{
static vector<element>::iterator it;
// set it to a right answer
if(it<result.begin() || it>=result.end() )
it=result.begin();
if( it!=result.end() ){
if(!it->expr.str().empty())it->show_expr();
else it->show_data();
cout<<" = " <<target<<endl;
it++;
}else cout<<"no other solutions found!"<<endl;
}
void NumberGame::show_all_answers()
{
vector<element>::iterator it;
if(result.empty())cout<<"no solutions found!"<<endl;
else{
for(it=result.begin();it!=result.end();it++){
if(!it->expr.str().empty()) it->show_expr();
else it->show_data();
cout<<" = "<<target<<endl;
}
cout<<"--------------------"<<endl;
cout<<"solutions found: "<<result.size()<<endl;
}
}
bool NumberGame::random()
{
cout<<"Generating puzzle ... "<<endl;
generate();
show_puzzle();
show_keypress();
char ch;
while(1){
cin.clear();
cin.get(ch);
switch(ch)
{
case 'a':
show_one_answer();
break;
case 'A':
show_all_answers();
break;
case 'n':
case 'N':
generate();
show_puzzle();
show_keypress();
break;
case 'q':
case 'Q':
return false;
break;
default:
cout<<": ";
break;
}
}
return true;
}
void NumberGame::cal_target( vector<element> vt )
{
vector<element>::iterator it,it1,it2;
if(vt.empty())return;
if(vt.size()==1){
element e=vt.back();
if(e.data==target)result.push_back(e);
return;
}
for(it1=vt.begin(); it1<vt.end()-1; it1++){
for(it2=it1+1; it2<vt.end(); it2++){
element e1=*it1;
element e2=*it2;
it2=vt.erase(it2); // remove 2 elements
it1=vt.erase(it1); // CAUTION: e2 should erase first !
vt.push_back(e1+e2);
cal_target(vt);
vt.pop_back();
vt.push_back(e1-e2);
cal_target(vt);
vt.pop_back();
vt.push_back(e2-e1);
cal_target(vt);
vt.pop_back();
vt.push_back(e1*e2);
cal_target(vt);
vt.pop_back();
if(e2.data){
vt.push_back(e1/e2);
cal_target(vt);
vt.pop_back();
}
if(e1.data){
vt.push_back(e2/e1);
cal_target(vt);
vt.pop_back();
}
it1=vt.insert(it1,e1); // recover vector
it2=vt.insert(it2,e2); // CAUTION: e1 should insert first !
}
}
return;
}
int main()
{
NumberGame game;
cout<<"[1] user input"<<endl;
cout<<"[2] random test" <<endl;
cout<<"[0] quit"<<endl;
cout<<"select the number(0/1/2): ";
char ch;
cin.get(ch);
cin.clear();
switch(ch){
case '1':
while(game.input() && game.output());
break;
case '2':
game.random();
break;
default:
return 0;
}
}
|