24点游戏规则：
给玩家4张牌，每张牌面值在1-13之间，允许其中有数值相同的牌，采用加、减、乘、除四则运算，允许中间运算存在小数，并且可以使用括号，但每张牌只能使用一次，尝试构造一个表达式，使其运算结果为24.
要依据上述游戏规则构造一个玩24点游戏的算法。
输入：num1 , num2 , num3 , num4
输出：若能得到运算结果为24，则输出一个对应的运算表达式。
如
输入11,8,3,5
输出（11-8）*（3+5）=24
解法一：穷举法
遍历运算符、数字和括号的所有排列组合形式。对于4个数，每个数使用一次，则有4！=24种全排，4个数的四则运算可以重复，则有4^3（4个数运算需要3个运算符），因此不考虑括号情况下有4！*4^3=1536种表达式。考虑括号的情况有五种情况(((AB)C)D)、((AB)(CD))、((A(BC))D)、(A((BC)D))、(A(B(CD)))，因此总共需要穷举1536*5=7680种。
设f(A)代表集合A经过四则运算所能得到的结果集合，则可以采用如下分而治之的思想：
对A先取两个数，进行四则运算后得到的集合取并即可。
如：A={1,2,3,4} 先取出1和2，计算出结果后将结果放回原集合中，得到五个不同的集合B={3,3,4}，C={-1,3,4}，D={1,3,4} E = {2,3,4}，F={1/2,3,4}。则可以递归的定义：f（A）=f（B）并f（C）并f（D）并f（E）并f（F），算法的代码如下所示：
//下面代码是24点游戏的解法一：穷举法
// 输入：四个数字数组numbers[4]
// 输出：可以得到24点，则返回一个表达式结果为24const int cardsNum = 4;const int resultValue = 24;const double Eps = 1E-6; //由于浮点运算会有精度误差，所以用一个很小的数作为容差值string result[cardsNum];//存放结果表达式bool PointsSet(int n , double numbers[] )
{if(n == 1){//递归终止条件if(fabs(numbers[0]-resultValue) < Eps){//找到24点的一个合法算式cout<<result[0]<<endl;return true;}else{return false;}}else{//取出两个数进行四则运算，递归的求解for(int i=0 ; i<cardsNum ; i++)//任取两个数for(int j=i+1 ; j<cardsNum ; j++){double a = numbers[i];//第一个数double b = numbers[j];//第二个数string res1 = result[i];//第一个表达式string res2 = result[j];//第二个表达式//进行加法运算a+bnumbers[i] = a+b ; //第一个数存放结果numbers[j] = numbers[n-1];//第二个数存放最后一个数result[i] = '(' + res1 + '+' + res2 + ')';result[j] = result[n-1];if(PointsSet(n-1 , numbers))//递归的计算，如果计算结果不为24，则尝试下一种四则预算return true;//进行减法运算a-bnumbers[i] = a-b;numbers[j] = numbers[n-1];result[i] = '(' + res1 + '-' + res2 + ')';result[j] = result[n-1];if(PointsSet(n-1 , numbers))return true;//进行减法运算b-anumbers[i] = b-a;numbers[j] = numbers[n-1];result[i] = '(' + res2 + '-' + res1 + ')';result[j] = result[n-1];if(PointsSet(n-1 , numbers))return true;//进行乘法运算a*bnumbers[i] = a*b;numbers[j] = numbers[n-1];result[i] = '(' + res1 + '*' + res2 + ')';result[j] = result[n-1];if(PointsSet(n-1 , numbers))return true;//进行除法运算a/bif(b != 0){numbers[i] = a/b;numbers[j] = numbers[n-1];result[i] = '(' + res1 + '/' + res2 + ')';result[j] = result[n-1];if(PointsSet(n-1 , numbers))return true;}//进行除法运算b/aif(a != 0){numbers[i] = b/a;numbers[j] = numbers[n-1];result[i] = '(' + res2 + '/' + res1 + ')';result[j] = result[n-1];if(PointsSet(n-1 , numbers))return true;}//如果遍历本步所有四则运算结果24都没有出现，则退回上步。复原numbers[i] = a;numbers[j] = b;result[i] = res1;result[j] = res2;}return false;}
}int main(int argc, char const *argv[])
{double numbers[cardsNum];cout<<"输入：四个数字数组numbers"<<endl;for(int i=0 ; i<cardsNum ; i++){cin>>numbers[i];char buffer[20];_itoa_s(numbers[i] , buffer , 10);result[i] = buffer;}if(PointsSet(cardsNum , numbers))cout<<"Success"<<endl;else cout<<"Fail"<<endl;return 0;
}
解法二：分治法
解法一中存在大量的冗余计算，可以使用分治法将集合A分为非空真子集Ai和另外一部分A-Ai，当Ai穷尽所有A的真子集的时候，f(A)=并Fork(f(Ai) ,f(A-Ai));，其中Fork()含义是解法一中实现的六种运算结果（因为对于减法和除法，不同的运算次序得到结果不同）。f(A)定义为A集合中经过四则运算得到的结果集合。
下面是伪代码：
//伪代码实现24点游戏
//对于四个元素的集合A={a1,a2,a3,a4}，可以使用变量i来表示集合元素是否存在，如0111代表集合{a2,a3,a4}
//在main函数中调用 f((1<<cardsNum)-1)就可以递归的计算到f(i)(0<=i<=N-1)结果集，结果保存在S[i]中
//由定义可以知道f(0001)=a1、f(0010)=a2、f(0100)=a3、f(1000)=a4。所以初始化S集合时要注意以此作为递归截止条件
//S[i]=f(i)即S集合每个元素是f(i)的结果集。最终在S[15]中寻找是否有24的存在，有的话说明可以得到24点
24Game(Array)//Array为输入，每个元素为ai(0<=i<=N-1)
{for(i=0 ; i<2^N ; i++)S[i].clear();//初始化S集合for(int i=0 ; i<N ; i++)S[1<<i]=ai;for(i=0 ; i<2^N ; i++)S[i]=f[i];s[2^N-1].find(24);//查找是否有24点的存在
}
set f(int i)
{if(S[i].size())//memoreturn S[i];for(x=1 ; x<i ; x++)//遍历所有非空真子集if((x&i) == x){//x代表集合是i代表集合的非空真子集S[i] = Fork(f(x) , f(i-x));}
}下面是实现代码，参考：http://blog.csdn.net/tianshuai1111/article/details/7713640
//下面给出24点游戏的具体代码
//采用C++的set作为S[]集合
const int cardsNum = 4;
const double Eps = 1E-6;
const int RES = 24;struct ELEM{ELEM(double r , string& i):result(r),info(i) {}ELEM(double r , char *i):result(r),info(i){}double result;//运算出的结果string info;//运算过程bool operator<(const ELEM &m)const{//在set的红黑树插入需要比较操作return this->result<m.result;}
};
set<ELEM> vset[1<<cardsNum];//一定要放在struct定义的后面，否则编译器无法知道set中类型是什么
set<ELEM>& f(int i)//i二进制形式代表A真子集,返回一个集合
{if(vset[i].size())//memoreturn vset[i];for(int x=1 ; x<i/2 ; x++){//遍历所有非空真子集，由分治的对称性，只分一半if((x&i) == x){//x是i的一个真子集string str;set<ELEM>& s1 = f(x);set<ELEM>& s2 = f(i-x);set<ELEM>::iterator iter1;set<ELEM>::iterator iter2;for(iter1=s1.begin() ; iter1!=s1.end() ; iter1++)for(iter2=s2.begin() ; iter2!=s2.end() ; iter2++){//两元素的六项运算存入对应的vset[i]中str = '(' + iter1->info +'+' + iter2->info + ')';vset[i].insert(ELEM(iter1->result+iter2->result , str));str = '(' + iter1->info +'-' + iter2->info + ')';vset[i].insert(ELEM(iter1->result-iter2->result , str));str = '(' + iter2->info +'-' + iter1->info + ')';vset[i].insert(ELEM(iter2->result-iter1->result , str));str = '(' + iter1->info +'*' + iter2->info + ')';vset[i].insert(ELEM(iter1->result*iter2->result , str));if(abs(iter1->result) > Eps){//第一个数不为0str = '(' + iter2->info +'/' + iter1->info + ')';vset[i].insert(ELEM(iter2->result/iter1->result , str));}if(abs(iter2->result) > Eps){//第二个数不为0str = '(' + iter1->info +'/' + iter2->info + ')';vset[i].insert(ELEM(iter1->result/iter2->result , str));}}}}return vset[i];
}int main()
{cout<<"请输入4个数字："<<endl;int numbers[cardsNum];for(int i=0 ; i<cardsNum ; i++)cin>>numbers[i];for(int i=0 ; i<cardsNum ; i++){//初始化vset[15]集合,置vset[2^i].result = ai;char buffer[10];sprintf_s(buffer , "%d" , numbers[i]);vset[1<<i].insert(ELEM(numbers[i] , buffer));}set<ELEM> resultSet = f((1<<cardsNum)-1);set<ELEM> ::iterator iter;for(iter=resultSet.begin() ; iter!=resultSet.end() ; iter++){if(iter->result == RES)cout<<iter->info<<endl;}}