Massive Algorithms: Compute 24 每日一题(13)――24点 (分治&递归)

Compute 24 每日一题(13)――24点 (分治&递归)

Related: HDU 1427 速算24点-DFS
给玩家4张牌，每张面值1~13，采用+、-、*、/以及括号，使其最终结果为24
http://coderchen.blogspot.com/2015/11/compute-24.html
dfs搜索搞定。。。但是这里要注意一些细节，每次计算得到新的数之后最好加入数组做下一次搜索，不然容易出错。

 private boolean compute(int[] nums, int target) {

  boolean[] visit = new boolean[nums.length];

  return helper(nums, visit, target, nums.length);

}

 private boolean helper(int[] nums, boolean[] visit, int target, int c) {

  if (c == 1) {

   for (int i = 0; i < nums.length; i++) {

    if (!visit[i]) {

     return nums[i] == target;

}

}

  } else {

   for (int i = 0; i < nums.length; i++) {

    if (visit[i])

     continue;

    for (int j = i + 1; j < nums.length; j++) {

     if (visit[j])

      continue;

     int n1 = nums[i];

     int n2 = nums[j];

     visit[j] = true;

     nums[i] = n1 + n2;

     if (helper(nums, visit, target, c - 1))

      return true;

     nums[i] = n1 - n2;

     if (helper(nums, visit, target, c - 1))

      return true;

     nums[i] = n2 - n1;

     if (helper(nums, visit, target, c - 1))

      return true;

     nums[i] = n1 * n2;

     if (helper(nums, visit, target, c - 1))

      return true;

     if (n2 != 0) {

      nums[i] = n1 / n2;

      if (helper(nums, visit, target, c - 1))

       return true;

}

     if (n1 != 0) {

      nums[i] = n2 / n1;

      if (helper(nums, visit, target, c - 1))

       return true;

}

     nums[i] = n1;

     visit[j] = false;

}

}

}

  return false;

}

2.分治法

假定集合A={1,2,3,4},首先任意取出两个数，如去除1,2，A=A - {1,2},进行不同的四则运算，1+2=3,1-2=-1, 1*2=2, 1/2=0.5, 将结果再分别加入集合A，可得：

B={3,3,4}, C={-1,3,4}, D={2,3,4}, E={0.5,3,4}四个新的集合：

集合A所有可能的值 F(A) = F(B)+F(C)+F(D)+F(E) 计算规模由4个数降低为3个数

F(Array)
{
if(Array.Length<2)
{
if(最终结果为24) 输出表达式;
else 无法构造
}
for each(从数组中任意取两个数的组合)
{
for each(运算符（+, -, *, /）)
{
1.计算该组合在此运算符下的结果；
2.将组合中的两个数从原数组中移除，并将步骤1的结果放入数组；
3.对新数组递归调用f，找到一个表达式则返回；
4.将步骤1的结果移除，并将该组合中的两个数重新放回该数组；
}
}
}

3.采用分支限界法求解

任然假定假定集合A，首先采用分治思想，将集合A划分为A1与A-A1,分别对他们俩进行四则运算求解F(A1)和F(A-A1)，最后对这两个集合里的元素进行四则运算，所得到的所有集合的并集就是F(A)

#define N 4 // 4张牌，可变
#define RES 24 // 运算结果为24，可变
#define EPS 1e-6
struct Elem
{
Elem(double r, string& i):res(r),info(i){}
Elem(double r, char* i):res(r),info(i){}
double res; // 运算出的数据
string info; // 运算的过程
bool operator<(const Elem& e) const
{
return res < e.res; // 在set的红黑树插入操作中需要用到比较操作
}
};
int A[N]; // 记录N个数据
//用二进制数来表示集合和子集的概念，0110表示集合包含第2,3个数
set<Elem> vset[1<<N]; // 包含4个元素的集合共有16个子集0-15
set<Elem>& Fork(int m)
{
// memo递归
if (vset[m].size())
{
return vset[m];
}
for (int i=1; i<=m/2; i++)//因为分别计算Fork(i)与Fork(m-i)，所以计算一半就行了
if ((i&m) == i)
{
set<Elem>& s1 = Fork(i);
set<Elem>& s2 = Fork(m-i);
// 得到两个子集合的笛卡尔积，并对结果集合的元素对进行6种运算
for (set<Elem>::iterator cit1=s1.begin(); cit1!=s1.end(); cit1++)
for (set<Elem>::iterator cit2=s2.begin(); cit2!=s2.end(); cit2++)
{
string str;
str = "("+cit1->info+"+"+cit2->info+")";
vset[m].insert(Elem(cit1->res+cit2->res,str));
str = "("+cit1->info+"-"+cit2->info+")";
vset[m].insert(Elem(cit1->res-cit2->res,str));
str = "("+cit2->info+"-"+cit1->info+")";;
vset[m].insert(Elem(cit2->res-cit1->res,str));
str = "("+cit1->info+"*"+cit2->info+")";
vset[m].insert(Elem(cit1->res*cit2->res,str));
if (abs(cit2->res)>EPS)
{
str = "("+cit1->info+"/"+cit2->info+")";
vset[m].insert(Elem(cit1->res/cit2->res,str));
}
if (abs(cit1->res)>EPS)
{
str = "("+cit2->info+"/"+cit1->info+")";
vset[m].insert(Elem(cit2->res/cit1->res,str));
}
}
}
return vset[m]; //这一步一定不要忘了
}
int main()
{
int i;
for (i=0; i<N; i++)
cin >> A[i];
// 递归的结束条件;
for (i=0; i<N; i++)
{
char str[10];
sprintf(str,"%d",A[i]);
vset[1<<i].insert(Elem(A[i],str));
}
Fork((1<<N)-1);//开始1111 表示四个数;
// 显示算出24点的运算过程;
for (set<Elem>::iterator it=vset[(1<<N)-1].begin(); it!=vset[(1<<N)-1].end(); it++)
{
if (abs(it->res-RES) < EPS)
cout << it->info << endl;
}
}

http://blog.csdn.net/tianshuai1111/article/details/7713640

最直接的方法就是采用穷举法，游戏中可用的运算符只有四种，四个数字每个只能使用一次。

1）不考虑括号情况

4个数全排列：4！=24种

需要三个运算符，且运算符可以重复：4*4*4=64

总计：1536

2）考虑括号（是个难点）

自己想的加括号：四个数有五种加括号方式： (AB)CD 、 AB(CD)、 A(BC)D 、 A((BC)D) 、 (AB)(CD)、A(B(CD))

错误点：这里添加括号的时候，需要把四个数都看成相乘。需要加两个括号来列举比较直观

AB(CD) = (AB)(CD)

改正后：((AB)C)D 、 (AB)(CD) 、 (A(BC))D 、 A((BC)D) 、A(B(CD))

http://bylijinnan.iteye.com/blog/1606892

* 1.穷举。计算所有的可能，若能得到24，输出

public static boolean compute(double[] number,String[] result,int n){
if(n==1){
return (Math.abs(number[0]-ResultValue)<DIFF); //number[0]==ResultValue or not
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
double a=number[i];
double b=number[j];
String expa=result[i];
String expb=result[j];
//每计算一次，参与运算的数字就少一个。将最后一个数字复制到位置j,可达到缩小（缩短）数组的效果
number[j]=number[n-1];
result[j]=result[n-1];
//加法操作 a+b
number[i] = a+b;
result[i] = '(' + expa + '+' + expb + ')';
if(compute(number,result,n-1)){
return true;
}
//减法操作 a-b
number[i] = a - b;
result[i] = '(' + expa + '-' + expb + ')';
if(compute(number,result,n-1)){
return true;
}
//减法操作 b-a
number[i] = b - a;
result[i] = '(' + expb + '-' + expa + ')';
if(compute(number,result,n-1)){
return true;
}
//乘法操作 a*b
number[i] = a * b;
result[i] = '(' + expa + '*' + expb + ')';
if(compute(number,result,n-1)){
return true;
}
//除法操作 a/b, 如果除数不为0
if(b != 0){
number[i] = a / b;
result[i] = '(' + expa + '/' + expb + ')';
if(compute(number,result,n-1))
{
return true;
}
}
//除法操作 b/a , 如果除数不为0
if(a != 0){
number[i] = b / a;
result[i] = '(' + expb + '/' + expa + ')';
if(compute(number,result,n-1)){
return true;
}
}
number[i] = a;
number[j] = b;
result[i] = expa;
result[j] = expb;
}
}
return false;
}

http://www.cnblogs.com/TenosDoIt/p/3407636.html
http://www.cnphp6.com/archives/23939

算法1：

算法1代码如下，我在原来的基础上做了一点改动1、从数组中任选两个数时，保证数对前面没有选择过； 2、通过运算符优先级去除多余的括号；3、选出的两个数相同时，减法和除法只做一次，即只做a-b ,a/b, 不做 b-a,b/a，其中1、3都可以减少冗余计算

 10 //cards[i]的值是通过表达式expr[i]计算而来
 11 //且expr的最后一个运算操作lastop[i]
 12 bool GameRecur(double cards[], string expr[], char lastop[],
 13                const int cardsNum, const int result)
 14 {
 15     if(cardsNum == 1)
 16     {
 17         if(cards[0] == result)
 18         {
 19             //cout<<expr[0]<<endl;
 20             return true;
 21         }
 22         else return false;
 23     }
 24     //从已有数中任选两个,计算得到中间结果，并且和剩余的数一起存在cards数组的前
 25     //cardsNum-1个位置
 26     map<pair<double,double>,bool> selectedPair;
 27     for(int i = 0; i<cardsNum; i++)
 28     {
 29         for(int k  = i+1; k < cardsNum; k++)
 30         {
 31             if( selectedPair.find(pair<double, double>(cards[i], cards[k]))
 32                != selectedPair.end() || selectedPair.find(pair<double, double>
 33                (cards[k], cards[i])) != selectedPair.end() )
 34                 break;
 35             else
 36             {
 37                 selectedPair[pair<double,double>(cards[i], cards[k])] = 1;
 38                 selectedPair[pair<double,double>(cards[k], cards[i])] = 1;
 39             }
 40             //上面的代码保证选出的数对不重复
 41             double a = cards[i], b = cards[k];
 42             cards[k] = cards[cardsNum-1];
 43             string expra = expr[i], exprb = expr[k];
 44             expr[k] = expr[cardsNum-1];
 45             char lastop_a = lastop[i], lastop_b = lastop[k];
 46             lastop[k] = lastop[cardsNum-1];
 47 
 48             cards[i] = a + b;
 49             expr[i] = expra + '+' + exprb;
 50             lastop[i] = '+';
 51             if(GameRecur(cards, expr, lastop, cardsNum-1, result))
 52                 return true;
 53 
 54             cards[i] = a - b;
 55             if('+' == lastop_b || '-' == lastop_b)
 56                 expr[i] = expra + '-' + '(' + exprb + ')';
 57             else expr[i] = expra + '-' + exprb;
 58             lastop[i] = '-';
 59             if(GameRecur(cards, expr, lastop, cardsNum-1, result))
 60                 return true;
 61 
 62             if(a != b)
 63             {
 64                 cards[i] = b - a;
 65                 if('+' == lastop_a || '-' == lastop_a)
 66                     expr[i] = exprb + '-' + '(' + expra + ')';
 67                 else expr[i] = exprb + '-' + expra;
 68                 lastop[i] = '-';
 69                 if(GameRecur(cards, expr, lastop, cardsNum-1, result))
 70                     return true;
 71             }
 72 
 73             cards[i] = a * b;
 74             if('-' == lastop_a || '+' == lastop_a)
 75                 expr[i] = '(' + expra + ')' + '*';
 76             else expr[i] = expra + '*';
 77             if('*' == lastop_b || ' ' == lastop_b)
 78                 expr[i] += exprb;
 79             else expr[i] += '(' + exprb + ')';
 80             lastop[i] = '*';
 81             if(GameRecur(cards, expr, lastop, cardsNum-1, result))
 82                 return true;
 83 
 84             if(b != 0)
 85             {
 86                 cards[i] = a / b;
 87                 if('-' == lastop_a || '+' == lastop_a)
 88                     expr[i] = '(' + expra + ')' + '/';
 89                 else expr[i] = expra + '/';
 90                 if(' ' == lastop_b)
 91                     expr[i] += exprb;
 92                 else expr[i] += '(' + exprb + ')';
 93                 lastop[i] = '/';
 94                 if(GameRecur(cards, expr, lastop, cardsNum-1, result))
 95                     return true;
 96             }
 97 
 98             if(a != 0 && a!= b)
 99             {
100                 cards[i] = b / a;
101                 if('-' == lastop_b || '+' == lastop_b)
102                     expr[i] = '(' + exprb + ')' + '/';
103                 else expr[i] = exprb + '/';
104                 if(' ' == lastop_a)
105                     expr[i] += expra;
106                 else expr[i] += '(' + expra + ')';
107                 lastop[i] = '/';
108                 if(GameRecur(cards, expr, lastop, cardsNum-1, result))
109                     return true;
110             }
111 
112             //把选出来的两个数放回原位
113             cards[i] = a;
114             cards[k] = b;
115             expr[i] = expra;
116             expr[k] = exprb;
117             lastop[i] = lastop_a;
118             lastop[k] = lastop_b;
119         }
120     }
121     return false;
122 }

对算法1稍作修改可以输出全部的表达式：

//cards[i]的值是通过表达式expr[i]计算而来
  3 //且expr的最后一个运算操作lastop[i]
  4 bool GameRecur_all(double cards[], string expr[], char lastop[],
  5                    const int cardsNum, const int result)
  6 {
  7     if(cardsNum == 1)
  8     {
  9         if(cards[0] == result)
 10         {
 11             cout<<expr[0]<<endl;
 12             return true;
 13         }
 14         else return false;
 15     }
 16     //从已有数中任选两个,计算得到中间结果，并且和剩余的数一起存在cards数组的前
 17     //cardsNum-1个位置
 18     map<pair<double,double>,bool> selectedPair;
 19     bool res = false;
 20     for(int i = 0; i<cardsNum; i++)
 21     {
 22         for(int k  = i+1; k < cardsNum; k++)
 23         {
 24             if( selectedPair.find(pair<double, double>(cards[i], cards[k]))
 25                != selectedPair.end() || selectedPair.find(pair<double, double>
 26                (cards[k], cards[i])) != selectedPair.end() )
 27                 break;
 28             else
 29             {
 30                 selectedPair[pair<double,double>(cards[i], cards[k])] = 1;
 31                 selectedPair[pair<double,double>(cards[k], cards[i])] = 1;
 32             }
 33             //上面的代码保证选出的数对不重复
 34             double a = cards[i], b = cards[k];
 35             cards[k] = cards[cardsNum-1];
 36             string expra = expr[i], exprb = expr[k];
 37             expr[k] = expr[cardsNum-1];
 38             char lastop_a = lastop[i], lastop_b = lastop[k];
 39             lastop[k] = lastop[cardsNum-1];
 40 
 41             cards[i] = a + b;
 42             expr[i] = expra + '+' + exprb;
 43             lastop[i] = '+';
 44             res = GameRecur_all(cards, expr, lastop, cardsNum-1, result)
 45                 || res;
 46 
 47             cards[i] = a - b;
 48             if('+' == lastop_b || '-' == lastop_b)
 49                 expr[i] = expra + '-' + '(' + exprb + ')';
 50             else expr[i] = expra + '-' + exprb;
 51             lastop[i] = '-';
 52             res = GameRecur_all(cards, expr, lastop, cardsNum-1, result) || res;
 53 
 54             if(a != b)
 55             {
 56                 cards[i] = b - a;
 57                 if('+' == lastop_a || '-' == lastop_a)
 58                     expr[i] = exprb + '-' + '(' + expra + ')';
 59                 else expr[i] = exprb + '-' + expra;
 60                 lastop[i] = '-';
 61                 res = GameRecur_all(cards, expr, lastop, cardsNum-1, result)
 62                     || res;
 63             }
 64 
 65             cards[i] = a * b;
 66             if('-' == lastop_a || '+' == lastop_a)
 67                 expr[i] = '(' + expra + ')' + '*';
 68             else expr[i] = expra + '*';
 69             if('*' == lastop_b || ' ' == lastop_b)
 70                 expr[i] += exprb;
 71             else expr[i] += '(' + exprb + ')';
 72             lastop[i] = '*';
 73             res = GameRecur_all(cards, expr, lastop, cardsNum-1, result)
 74                 || res;
 75 
 76             if(b != 0)
 77             {
 78                 cards[i] = a / b;
 79                 if('-' == lastop_a || '+' == lastop_a)
 80                     expr[i] = '(' + expra + ')' + '/';
 81                 else expr[i] = expra + '/';
 82                 if(' ' == lastop_b)
 83                     expr[i] += exprb;
 84                 else expr[i] += '(' + exprb + ')';
 85                 lastop[i] = '/';
 86                 res = GameRecur_all(cards, expr, lastop, cardsNum-1, result)
 87                     || res;
 88             }
 89 
 90             if(a != 0 && a!= b)
 91             {
 92                 cards[i] = b / a;
 93                 if('-' == lastop_b || '+' == lastop_b)
 94                     expr[i] = '(' + exprb + ')' + '/';
 95                 else expr[i] = exprb + '/';
 96                 if(' ' == lastop_a)
 97                     expr[i] += expra;
 98                 else expr[i] += '(' + expra + ')';
 99                 lastop[i] = '/';
100                 res = GameRecur_all(cards, expr, lastop, cardsNum-1, result)
101                      || res;
102             }
103 
104             //把选出来的两个数放回原位
105             cards[i] = a;
106             cards[k] = b;
107             expr[i] = expra;
108             expr[k] = exprb;
109             lastop[i] = lastop_a;
110             lastop[k] = lastop_b;
111         }
112     }
113     return res;
114 }

算法2

算法2代码如下，集合用stl中的set表示，代码中变量名保持和书中一致

调用函数PointGame2即可返回表达式结果，调用方式同算法1

10 struct setNode
11 {
12     double val;
13     string expr;//运算出val的表达式
14     setNode(double v, string e):val(v),expr(e){}
15     setNode(double v, char e[]):val(v),expr(e){}
16     bool operator < (const setNode &s)const
17     {
18         return val < s.val;
19     }
20 };
21 
22 void f(const int i, set<setNode> s[], const double result)
23 {
24     int len = sizeof(s)/sizeof(set<setNode>) - 1;//len = 2^n - 1
25     if(s[i].empty() == true)
26         for(int x = 1; x <= i/2; x++)
27             if((x&i) == x)
28             {
29                 set<setNode>::iterator it1, it2;
30                 // s[i] U= fork(s[x] ,s[i-x])
31                 for(it1 = s[x].begin(); it1 != s[x].end(); it1++)
32                     for(it2 = s[i-x].begin(); it2 != s[i-x].end(); it2++)
33                     {
34                         string expr;
35                         double tempresult;
36                         tempresult = it1->val + it2->val;
37                         expr = '(' + it1->expr + '+' + it2->expr + ')';
38                         s[i].insert(setNode(tempresult, expr));
39                         //计算f[2^n-1]时，若计算好了结果则可以停止
40                         if(i == len && tempresult == result)return;
41 
42 
43                         tempresult = it1->val - it2->val;
44                         expr = '(' + it1->expr + '-' + it2->expr + ')';
45                         s[i].insert(setNode(tempresult, expr));
46                         if(i == len && tempresult == result)return;
47                         if(it1->val != it2->val)
48                         {
49                             tempresult = it2->val - it1->val;
50                             expr = '(' + it2->expr + '-' + it1->expr + ')';
51                             s[i].insert(setNode(tempresult, expr));
52                             if(i == len && tempresult == result)return;
53                         }
54 
55                         tempresult = it1->val * it2->val;
56                         expr = '(' + it1->expr + '*' + it2->expr + ')';
57                         s[i].insert(setNode(tempresult, expr));
58                         if(i == len && tempresult == result)return;
59 
60                         if(it2->val != 0)
61                         {
62                             tempresult = it1->val / it2->val;
63                             expr = '(' + it1->expr + '/' + it2->expr + ')';
64                             s[i].insert(setNode(tempresult, expr));
65                             if(i == len && tempresult == result)return;
66                         }
67                         if(it1->val != it2->val && it1->val != 0)
68                         {
69                             tempresult = it2->val / it1->val;
70                             expr = '(' + it2->expr + '/' + it1->expr + ')';
71                             s[i].insert(setNode(tempresult, expr));
72                             if(i == len && tempresult == result)return;
73                         }
74                     }
75             }
76 }
77 
78 string PointGame2(int cards[], const int cardsNum, const int result)
79 {
80     int len = 1<<cardsNum;
81     set<setNode> S[len]; //对应文章中的数组S
82     //初始化只有一个元素的子集，j = 2^i，即只有一个2进制位是1
83     for(int i = 0, j = 1; i < cardsNum; i++, j = j<<1)
84     {
85         char buf[30];
86         sprintf(buf, "%d", cards[i]);
87         S[j].insert(setNode(cards[i],buf));
88     }
89     for(int i = 1; i <= len - 1; i++)
90         f(i, S, result);
91     for(set<setNode>::iterator it = S[len-1].begin();
92         it != S[len-1].end(); it++)
93         {
94             if(it->val == result)
95                 return it->expr;
96         }
97     return "-1";
98 }

* 2.分治。引入集合，去重。另外，利用x=5=(0101)来表示(a0,a1,a2,a3)的子集(a1,a3)是非常巧妙的

//方法2
private static final int n=CardsNumber;
private static final int m=(1<<n)-1; //(10000)-1=(1111)=15
private static List<Node>[] S;
public static boolean compute(int[] number){
S=new ArrayList[m+1];
//(a0,a1,a2,a3)的子集(a0),(a1),(a2),(a3)只有一个元素，不用运算直接返回即可
for(int j=0;j<n;j++){
int v=number[j];
Node node=new Node((0.0+v),(""+v));
List<Node> Si=new ArrayList<Node>();
Si.add(node);
int i=1<<j;
S[i]=Si;
}
for(int i=1;i<=m;i++){
List<Node> Si=fun(i);
S[i]=Si;
}
List<Node> Sm=S[m];
for(Node v:Sm){
if(Math.abs(v.value-ResultValue)<DIFF){
System.out.println("2. "+v.exp);
return true;
}
}
return false;
}
//递归求S[i]
public static List<Node> fun(int i){
List<Node> si=S[i];
if(si!=null&&!si.isEmpty()){
return si;
}
si=new ArrayList<Node>();
for(int x=1;x<i;x++){
if((x&i)==x){ //确保x是i的子集
List<Node> sx=fun(x);
List<Node> s_x=fun(i-x);
si.addAll(fork(sx,s_x));
}
}
return si;
}
//集合里元素两两运算并去重
public static List<Node> fork(List<Node> sx,List<Node> s_x){
Set<Node> set=new HashSet<Node>();
for(int i=0,m=sx.size();i<m;i++){
for(int j=0,n=s_x.size();j<n;j++){
Node a=sx.get(i);
Node b=s_x.get(j);
set.add(new Node(a.value+b.value,"("+a.exp+"+"+b.exp+")"));
set.add(new Node(a.value-b.value,"("+a.exp+"-"+b.exp+")"));
set.add(new Node(b.value-a.value,"("+b.exp+"-"+a.exp+")"));
set.add(new Node(a.value*b.value,"("+a.exp+"*"+b.exp+")"));
if(b.value!=0){
set.add(new Node(a.value/b.value,"("+a.exp+"/"+b.exp+")"));
}
if(a.value!=0){
set.add(new Node(b.value/a.value,"("+b.exp+"/"+a.exp+")"));
}
}
}
List<Node> si=new ArrayList<Node>(set);
return si;
}
static class Node{
double value; //表达式的值
String exp; //表达式
Node(double value,String exp){
this.value=value;
this.exp=exp;
}
public boolean equals(Object o) {
if (!(o instanceof Node))
return false;
Node node = (Node) o;
return Double.doubleToLongBits(this.value)==
Double.doubleToLongBits(node.value);
//&&this.exp.equals(node.exp); //只关心值是否相等，不关心表达式
}
public int hashCode() {
int result = 17;
long tolong = Double.doubleToLongBits(value);
result = 37 * result + (int) (tolong ^ (tolong >>> 32));
//result = 37 * result + exp.hashCode();
return result;
}
}

X. Iterative Version
http://www.iteye.com/topic/312476
24点游戏规则：任取1－9之间的4个数字，用＋－＊／（）连结成算式，使得式子的计算结果为24。估计很多人都玩过用扑克牌玩的那种，印象中10也算在内的，两人各出2张牌，谁先算出来谁赢，赢家收回已经算过的4张牌。最后看谁手里的牌多。
这个程序实现使用穷举的方法，将所有可能的排列穷举出来，最后将每个排列中计算出结果。计算结果时，将前两个作为一组、后两个数作为一组，分别计算出各组的结果，再对获得的两个组结果进行计算。由于是排列，分前后两组进行计算就可满足所有可能的计算。

public static void evaluate(int[] v){
int idx=0;
for(int a=0;a<4;a++)
for(int b=0;b<4;b++)
for (int c=0;c<4;c++)
for (int d=0;d<4;d++){
if (a!=b && a!=c && a!=d && b!=c && b!=d && c!=d){
idx++;
check(v,new int[]{a,b,c,d});
}
}
}
static char[] op={'+','-','*','/'};
public static void check(int[] v,int[] idx){
for(int o=0;o<4;o++){
for(int p=0;p<4;p++){
for(int t=0;t<4;t++){
if (op(op[p],op(op[o],v[idx[0]],v[idx[1]]),op(op[t],v[idx[2]],v[idx[3]]))==24){
System.out.println(String.format("(%1$d %2$c %3$d) %4$c (%5$d %6$c %7$d)",
v[idx[0]],op[o],v[idx[1]],op[p],v[idx[2]],op[t],v[idx[3]]));
}
}
}
}
}
public static int op(char op,int v1,int v2){
switch(op){
case '+':
return v1+v2;
case '-':
return v1-v2;
case '*':
return v1*v2;
case '/':
if (v2==0) return -111;
if (v1%v2!=0) return -111;
return v1/v2;
default:
return 0;
}
}

http://www.cppblog.com/flyinghearts/archive/2010/08/01/121907.html
bool calc(int src[], size_t N, double M = 24.0) 8

{ 9

if (N == 0 || src == NULL) return false;10

set<double> result[1 << N];11

for (size_t i = 0; i < N; ++i) result[1<<i].insert((double)src[i]); 12

for (size_t i =1; i < (1<<N); ++i) {14

for (size_t j = 1; j <= (i >> 1); ++j) {15

if ((i & j) != j) continue;16

for (set<double>::iterator p = result[j].begin(); p != result[j].end(); ++p) {17

double va = *p;18

size_t k = i ^ j;19

for (set<double>::iterator q = result[k].begin(); q != result[k].end(); ++q) {20

double vb = *q;21

result[i].insert(va + vb);22

result[i].insert(va - vb);23

result[i].insert(vb - va);24

result[i].insert(va * vb);25

if (vb != 0.0) result[i].insert(va / vb);26

if (va != 0.0) result[i].insert(vb / va);27

}
28

}
29

} 30

}
31

size_t j = (1 << N) - 1;33

const double zero = 1e-9;34

for (set<double>::iterator p = result[j].begin(); p != result[j].end(); ++p) {35

if (fabs(*p - M) < zero) return true;36

}
37

return false;38

}
http://www.oschina.net/code/snippet_1377254_35910
http://www.blogjava.net/comic222/archive/2009/01/06/250101.html
http://rosettacode.org/wiki/24_game/Solve#Java
Read full article from 每日一题(13)――24点 (分治&递归) - 小熊不去实验室 - 博客频道 - CSDN.NET

Compute 24 每日一题(13)――24点 (分治&递归)

Labels

Popular Posts