1.16 24点游戏

24点游戏的解决办法，也是采取穷举法的思路，4个数，有4！=24中排列的方法，然后3个操作符号，有4×4×4 = 64种结果，再加上括号，有5种结果，于是，每4个数有24*66*5 = 7680中结果。
为了简便计算，原书中给出的第一种方法采取这样一种递归的思路：
  1 /*
  2 <编程之美>
  3 深搜 
  4 遍历运算符， 数和括号的所有排列形式 
  5 */
  6 #include <iostream>
  7 #include <string>
  8 #include <math.h>
  9 
 10 using namespace std;
 11 
 12 const  double Threshold = 1e-6;
 13 const int CardsNumber = 4;
 14 const int ResultValue = 24;
 15 double number[CardsNumber];
 16 string result[CardsNumber];
 17 
 18 bool PointGame(int n)
 19 {
 20     if(n == 1)
 21     {
 22         if(fabs(number[0] - ResultValue) < Threshold)
 23         {
 24             cout << result[0] << endl;
 25             return true;
 26         }
 27         else
 28         {
 29             return false;
 30         }
 31     }
 32     
 33     for(int i = 0; i < n; i++)
 34     {
 35         for(int j = i +1 ; j < n; j++)
 36         {
 37             double a, b;
 38             string expa, expb;
 39             
 40             a = number[i];
 41             b = number[j];
 42             number[j] = number[n - 1];
 43             
 44             expa = result[i];
 45             expb = result[j];
 46             result[j] = result[n-1];
 47             
 48             //+加法操作 a+b
 49             number[i] = a + b;
 50             result[i] = '(' + expa + '+' + expb + ')';
 51             if(PointGame(n-1))
 52             {
 53                 return true;
 54             }
 55             
 56             //减法操作 a-b
 57             number[i] = a - b;
 58             result[i] = '(' + expa + '-' + expb + ')';
 59             if(PointGame(n-1))
 60             {
 61                 return true;
 62             }
 63             
 64             //减法操作 b-a
 65             number[i] = b - a;
 66             result[i] = '(' + expb + '-' + expa + ')';
 67             if(PointGame(n-1))
 68             {
 69                 return true;
 70             }
 71             
 72             //乘法操作 a*b 
 73             number[i] = a * b;
 74             result[i] = '(' + expa + '*' + expb + ')';
 75             if(PointGame(n-1))
 76             {
 77                 return true;
 78             }
 79             
 80             //除法操作 a/b, 如果除数不为0 
 81             if(b != 0)
 82             {
 83                 number[i] = a / b;
 84                 result[i] = '(' + expa + '/' + expb + ')';
 85                 if(PointGame(n-1))
 86                 {
 87                     return true;
 88                 }
 89             }                     
 90             
 91             //除法操作 b/a , 如果除数不为0 
 92             if(a != 0)
 93             {
 94                 number[i] = b / a;
 95                 result[i] = '(' + expb + '/' + expa + ')';
 96                 if(PointGame(n-1))
 97                 {
 98                     return true;
 99                 }
100             }
101             
102             number[i] = a;
103             number[j] = b;
104             result[i] = expa;
105             result[j] = expb;
106             
107         }
108     }
109     return false;
110     
111 }
112 
113 int main()
114 {
115     int x;
116     for(int i =0; i< CardsNumber; i++)
117     {
118         char buffer[20];
119         cout << "the " << i << "the number: ";
120         cin >> x;
121         number[i] = x;
122         itoa(x,buffer,10);
123         result[i] = buffer;
124 
125     }
126     
127     if(PointGame(CardsNumber))
128     {
129         cout << "Success" << endl;
130         
131     }
132     else
133     {
134         cout << "failure" << endl;
135     }
136     system("pause");    
137     return 0;
138 }