【编程之美】24点游戏

一，概述

二十四点是一种益智游戏，它能在游戏中锻炼人们的心算，它往往要求人们将四个数字进行加减乘除（允许使用括号）求得二十四。然后将四个数字的计算公式表示出来。

二，中缀表达式求解

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

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))

四个运算数五种不同加括号方式的由来。这是一个经典的Catalan数问题。

这个经典Catalan数问题在组合数学教材上都能找到。原题目是：n 个数相乘, 不改变它们的位置, 只用括号表示不同的相乘顺序，令g(n)表示这种条件下构成不同乘积的方法数，令C(n)表示第n个Catalan数。则有g(n)=C(n-1)。前几个Catalan数为：C(0)=1，C(1)=1，C(2)=2，C(3)=5，C(4)=14，C(5)=42。所以g(4)=C(3)=5。

根据Catalan数的计算公式，有g(4)=g(1)g(3)+g(2)g(2)+g(3)g(1)。

Catalan数的计算公式也同时提供了构造答案的方法。对于4个数，中间有3个位置，可以在任何一个位置一分为二，被分开的两半各自的加括号方案再拼凑起来就得到一种4个数的加括号方案：

一个数时：(A)，一种

两个数：g(2)=g(1)g(1)，所以是(A)(B)=(AB)，一种

三个数：g(3)=g(1)g(2)+g(2)g(1)=(A)(BC)+(AB)(C)，两种

四个数：g(4)=g(1)g(3)+g(2)g(2)+g(3)g(1)

=(A)[(B)(CD)+(BC)(D)]+(AB)(CD)+[(A)(BC)+(AB)(C)](D)

=A(B(CD)) + A((BC)D) + (AB)(CD) + (A(BC))D + ((AB)C)D

共有五种。于是写代码枚举这五种加括号的方式即可。这种方法只是一种能得到正确答案的方法，扩展性和效率都极差。而且生成的表达式中也有冗余括号。

  1 #include <iostream>
  2 #include <cmath>
  3 using namespace std;
  4 
  5 const double Threshold = 1E-6;
  6 const int CardsNumber = 4;
  7 const int ResultValue = 24;
  8 double number[CardsNumber];
  9 string result[CardsNumber];
 10 
 11 bool PointsGame(int n)
 12 {
 13      if(n == 1)
 14      {
 15           // 由于浮点数运算会有精度误差，所以用一个很小的数1E-6来做容差值
 16           // 本书2.6节中讨论了如何将浮点数转化为分数的问题
 17           if(fabs(number[0] - ResultValue) < Threshold)//结果等于24
 18           {
 19                cout << result[0] << endl;//输出表达式
 20                return true; 
 21           }
 22           else
 23           {
 24                return false;
 25           }
 26      }
 27 
 28      for(int i = 0; i < n; i++)//第一个数(计算时被两个数结果替换)
 29      {
 30           for(int j = i + 1; j < n; j++)//第二个数(计算时候被最后一个数替换)
 31           {
 32                double a, b;//存放计算的数
 33                string expa, expb;//存放表达式中两个数
 34 
 35                a = number[i];
 36                b = number[j];
 37                number[j] = number[n - 1];//去除第二个数
 38 
 39                expa = result[i];
 40                expb = result[j];
 41                result[j] = result[n - 1];//表达式去除
 42 
 43                result[i] = '(' + expa + '+' + expb + ')';
 44                number[i] = a + b;//去除第一个数
 45                if(PointsGame(n - 1))
 46                     return true;
 47 
 48                result[i] = '(' + expa + '-' + expb + ')';
 49                number[i] = a - b;
 50                if(PointsGame(n - 1))
 51                     return true;
 52 
 53                result[i] = '(' + expb + '-' + expa + ')';
 54                number[i] = b - a;
 55                if(PointsGame(n - 1))
 56                     return true;
 57 
 58                result[i] = '(' + expa + '*' + expb + ')';
 59                number[i] = a * b;
 60                if(PointsGame(n - 1))
 61                     return true;
 62 
 63                if(b != 0)
 64                {
 65                     result[i] = '(' + expa + '/' + expb + ')';
 66                     number[i] = a / b;
 67                     if(PointsGame(n - 1))
 68                          return true;
 69                }
 70                if(a != 0)
 71                {
 72                     result[i] = '(' + expb + '/' + expa + ')';
 73                     number[i] = b / a;
 74                     if(PointsGame(n - 1))
 75                          return true;
 76                }
 77 
 78                number[i] = a;//将本次循环的结果消除，继续测试下一对数
 79                number[j] = b;
 80                result[i] = expa;
 81                result[j] = expb;
 82           }
 83      }
 84      return false;
 85 }
 86 
 87 int main()
 88 {
 89     int x;
 90     for(int i = 0; i < CardsNumber; i++)
 91     {
 92          char buffer[20];
 93          cout << "the " << i << "th number:";
 94          cin >> x;
 95          number[i] = x;
 96          itoa(x, buffer, 10);
 97          result[i] = buffer;
 98     }
 99     if(PointsGame(CardsNumber))
100     {
101          cout << "Success." << endl;
102     }
103     else
104     {
105          cout << "Fail." << endl;
106     }
107 }

三，分支限界法求解

 1 #include <iostream>
 2 #include <set>
 3 #include <string>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 #define N    4    // 4张牌，可变
 8 #define RES    24    // 运算结果为24，可变
 9 #define EPS 1e-6
10 
11 struct Elem
12 {
13     Elem(double r, string& i):res(r),info(i){}
14     Elem(double r, char* i):res(r),info(i){}
15     double res;    // 运算出的数据
16     string info; // 运算的过程
17     bool operator<(const Elem& e) const
18     {
19         return res < e.res; // 在set的红黑树插入操作中需要用到比较操作
20     }
21 };
22 
23 int A[N];    // 记录N个数据
24 // 用二进制数来表示集合和子集的概念，0110表示集合包含第2,3个数
25 set<Elem> vset[1<<N];    // 包含4个元素的集合共有16个子集0-15
26 
27 set<Elem>& Fork(int m)
28 {
29     // memo递归
30     if (vset[m].size())
31     {
32         return vset[m];
33     }
34     for (int i=1; i<=m/2; i++)
35         if ((i&m) == i)
36         {
37             set<Elem>& s1 = Fork(i);
38             set<Elem>& s2 = Fork(m-i);
39             set<Elem>::iterator cit1;
40             set<Elem>::iterator cit2;
41             // 得到两个子集合的笛卡尔积，并对结果集合的元素对进行6种运算
42             for (cit1=s1.begin(); cit1!=s1.end(); cit1++)
43                 for (cit2=s2.begin(); cit2!=s2.end(); cit2++)
44                 {
45                     string str;
46                     str = "("+cit1->info+"+"+cit2->info+")";
47                     vset[m].insert(Elem(cit1->res+cit2->res,str));
48                     str = "("+cit1->info+"-"+cit2->info+")";
49                     vset[m].insert(Elem(cit1->res-cit2->res,str));
50                     str = "("+cit2->info+"-"+cit1->info+")";;
51                     vset[m].insert(Elem(cit2->res-cit1->res,str));
52                     str = "("+cit1->info+"*"+cit2->info+")";
53                     vset[m].insert(Elem(cit1->res*cit2->res,str));
54                     if (abs(cit2->res)>EPS) 
55                     {
56                         str = "("+cit1->info+"/"+cit2->info+")";
57                         vset[m].insert(Elem(cit1->res/cit2->res,str));
58                     }
59                     if (abs(cit1->res)>EPS)
60                     {
61                         str = "("+cit2->info+"/"+cit1->info+")";
62                         vset[m].insert(Elem(cit2->res/cit1->res,str));
63                     }
64                 }
65         }
66     return vset[m];
67 }
68 
69 int main()
70 {
71     int i;
72     for (i=0; i<N; i++)
73         cin >> A[i];
74     // 递归的结束条件
75     for (i=0; i<N; i++)
76     {
77         char str[10];
78         sprintf(str,"%d",A[i]);
79         vset[1<<i].insert(Elem(A[i],str));
80     }
81     Fork((1<<N)-1);//开始1111 表示四个数 
82     // 显示算出24点的运算过程
83     set<Elem>::iterator it;
84     for (it=vset[(1<<N)-1].begin(); 
85        it!=vset[(1<<N)-1].end(); it++)
86         {
87             if (abs(it->res-RES) < EPS)
88                 cout << it->info << endl;
89     }
90 }

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