24点，是指给定4个数，和一个值，如何将这4个数通过+-*/得到这个值。
一个算法是这样的：4个数字组成一个表达式还需要3个运算符，这样我们只要把这7个元素的所有排列求出来，然后求值就可以了。
但是这个算法有三个问题：
1.这样的表示出来的序列并非全部是合法的表达式，比如3344+-*
2.实际的表达式可以加括号，但是这个也无法体现出来，而且表达式计算起来还要考虑优先级，转化为后缀表达式，当然这个括号我们可以通过枚举+-*/的优先级别来代替加括号
3.数字是不能重复选择的，而运算符则可以重复
用一个改进后的算法：
我们枚举后缀表达式的所有可能，同时注意数字是不能重复选择的，而运算符则可以重复，对于不重复选择的枚举，通常的解决方式是通过定义一个bool数组，来表示当前选择的集合。对于后缀表达式，只要保证每个位置数字个数总是大于运算符个数，那它就是合法的，这样合法性很容易验证，同时不用考虑优先级的问题了。
这样的一个算法，仍然有优化空间：
1.数字仍然可能重复，因此它们的可能排列实际上并没有4!那么多
2.+和*具有交换性，这样1+4和4+1，(14+,41+)实际上结果相同，但如果枚举仍然可能把它们都枚举一遍。
针对1，可以采取这样的策略，首先假设所有的数字都是一样的，进行枚举，对于每个枚举出来的排列，再根据实际的数字，枚举这个数字的排列，实际上是个双阶段枚举
针对2，用后缀表达式比较难表示，可以考虑用表达式树来表示表达式，通过枚举可能的树及树中节点元素的分配，来完成，这样就比较容易排除重复的组合
还有一个方法，dp：
这个针对另一个问题比较好，8个8如何通过通过+-*/得到一个值n。
n个8的可能运算结果可以用(1,n-1)…个8的可能运算结果组合出来。
24点算法实现：
#include <cstdio>
using namespace std;
int n = 8;
//计算后缀表达式的值
double computer(int a[],int n){
/*
int num_n = 0;
int char_n = 0;
for(int i = 0 ; i < n-1 ; i++){
if(a[i] < 10)num_n++;
else char_n++;
if(char_n>=num_n)return -1;
}
if(num_n < 4) return -1;
*/
double stack[10];
int index = 0;
double res = 0;
for(int i = 0 ; i < n-1 ; i++){
switch(a[i]){
case ‘+’:
res = stack[index]+ stack[–index];
stack[index] = res;
break;
case ‘-‘:
res = stack[index-1]- stack[index];
–index;
stack[index] = res;
break;
case ‘*’:
res = stack[index]* stack[–index];
stack[index] = res;
break;
case ‘/’:
if(stack[index] == 0.0)return -1;
res = stack[index-1]/ stack[index];
–index;
stack[index] = res;
break;
default:
res = (double)a[i];
stack[++index] = (double)a[i];
;
}
//printf("%lf ",res);
}
return res;
}
/*
//最初那个算法的实现，但这个算法是有问题的。
int a[] = {3,3,8,8,’+’,’-‘,’*’,’/’};
void perm(int a[],int i){
if(i == n-1){
double res = computer(a,n);
//if(res-24.0 < 0.01 && res-24.0 > -0.01){
if(res != -1 && a[0] == 8){
for(int j = 0 ; j < n-1 ; j++){
if(a[j] < 10)
printf("%c",a[j]+’0′);
else
printf("%c",a[j]);
}
printf(" %lf",res);
printf("\n");
}
return;
}
for(int j = i ; j < n ; j++){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
perm(a,i+1);
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
*/
int suffix_a[10];
bool num_selected[]={false,false,false,false};
int num[4] ={1,2,3,4};
int op[4] ={‘+’,’-‘,’*’,’/’};
void perm2(int suffix_a[],int index,bool num_selected[],int num_n){
if(index >0 && num_n <= (index -num_n)) return;
if(num_n > 4) return;
if(index == n-1){
double res = computer(suffix_a,n);
if(res-24.0 < 0.01 && res-24.0 > -0.01){
//(res != -1 && suffix_a[0] == 8){
for(int j = 0 ; j < n-1 ; j++){
if(suffix_a[j] < 10)
printf("%c",suffix_a[j]+’0′);
else
printf("%c",suffix_a[j]);
}
printf(" %lf",res);
printf("\n");
}
return;
}
for(int i = 0; i < 4 ; i++){
suffix_a[index] = op[i];
perm2(suffix_a,index+1,num_selected,num_n);
}
for(int i = 0 ; i < 4 ; i++){
if(num_selected[i] == false){
suffix_a[index] = num[i];
num_selected[i] = true;
perm2(suffix_a,index+1,num_selected,num_n+1);
num_selected[i] = false;
}
}
}
int main(){
perm2(suffix_a,0,num_selected,0);
while(true);
}