程式設計之美-----24點遊戲

程式設計之美-----24點遊戲

問題：

給玩家4張牌，每張牌的面值在1-13之間，允許其中有數值相同的牌，采用加、減、乘、除四則運算，允許中間運算存在小數，并且可以使用括号，但每張牌隻能用一次。構造表達式，使其結果為24.

解法一: 具體見書分析,這裡利用了枚舉,通過遞歸解法.

1. #include <iostream>  
2. #include <cmath>  
3. using namespace std;  
4. const double Threshold = 1E-6;  
5. const int CardsNumber = 4;  
6. const int ResultValue = 24;  
7. double number[CardsNumber];  
8. string result[CardsNumber];  
9. bool PointsGame(int n)  
10. {  
11.      if(n == 1)  
12.      {  
13.           // 由于浮點數運算會有精度誤差，是以用一個很小的數1E-6來做容內插補點  
14.           // 本書2.6節中讨論了如何将浮點數轉化為分數的問題  
15.           if(fabs(number[0] - ResultValue) < Threshold)//結果等于24  
16.           {  
17.                cout << result[0] << endl;//輸出表達式  
18.                return true;   
19.           }  
20.           else  
21.           {  
22.                return false;  
23.           }  
24.      }  
25.      for(int i = 0; i < n; i++)//第一個數(計算時被兩個數結果替換)  
26.      {  
27.           for(int j = i + 1; j < n; j++)//第二個數(計算時候被最後一個數替換)  
28.           {  
29.                double a, b;//存放計算的數  
30.                string expa, expb;//存放表達式中兩個數  
31.                a = number[i];  
32.                b = number[j];  
33.                number[j] = number[n - 1];//去除第二個數  
34.                expa = result[i];  
35.                expb = result[j];  
36.                result[j] = result[n - 1];//表達式去除  
37.                result[i] = '(' + expa + '+' + expb + ')';  
38.                number[i] = a + b;//去除第一個數  
39.                if(PointsGame(n - 1))  
40.                     return true;  
41.                result[i] = '(' + expa + '-' + expb + ')';  
42.                number[i] = a - b;  
43.                if(PointsGame(n - 1))  
44.                     return true;  
45.                result[i] = '(' + expb + '-' + expa + ')';  
46.                number[i] = b - a;  
47.                if(PointsGame(n - 1))  
48.                     return true;  
49.                result[i] = '(' + expa + '*' + expb + ')';  
50.                number[i] = a * b;  
51.                if(PointsGame(n - 1))  
52.                     return true;  
53.                if(b != 0)  
54.                {  
55.                     result[i] = '(' + expa + '/' + expb + ')';  
56.                     number[i] = a / b;  
57.                     if(PointsGame(n - 1))  
58.                          return true;  
59.                }  
60.                if(a != 0)  
61.                {  
62.                     result[i] = '(' + expb + '/' + expa + ')';  
63.                     number[i] = b / a;  
64.                     if(PointsGame(n - 1))  
65.                          return true;  
66.                }  
67.                number[i] = a;//将本次循環的結果消除，繼續測試下一對數  
68.                number[j] = b;  
69.                result[i] = expa;  
70.                result[j] = expb;  
71.           }  
72.      }  
73.      return false;  
74. }  
75. int main()  
76. {  
77.     int x;  
78.     for(int i = 0; i < CardsNumber; i++)  
79.     {  
80.          char buffer[20];  
81.          cout << "the " << i << "th number:";  
82.          cin >> x;  
83.          number[i] = x;  
84.          itoa(x, buffer, 10);  
85.          result[i] = buffer;  
86.     }  
87.     if(PointsGame(CardsNumber))  
88.     {  
89.          cout << "Success." << endl;  
90.     }  
91.     else  
92.     {  
93.          cout << "Fail." << endl;  
94.     }  
95. }  

解法二:分支界限法

1. #include <iostream>  
2. #include <set>  
3. #include <string>  
4. #include <cmath>  
5. using namespace std;  
6. #define N   4   // 4張牌，可變  
7. #define RES 24  // 運算結果為24，可變  
8. #define EPS 1e-6  
9. struct Elem  
10. {  
11.     Elem(double r, string& i):res(r),info(i){}  
12.     Elem(double r, char* i):res(r),info(i){}  
13.     double res; // 運算出的資料  
14.     string info; // 運算的過程  
15.     bool operator<(const Elem& e) const  
16.     {  
17.         return res < e.res; // 在set的紅黑樹插入操作中需要用到比較操作  
18.     }  
19. };  
20. int A[N];   // 記錄N個資料  
21. // 用二進制數來表示集合和子集的概念，0110表示集合包含第2,3個數  
22. set<Elem> vset[1<<N];   // 包含4個元素的集合共有16個子集0-15  
23. set<Elem>& Fork(int m)  
24. {  
25.     // memo遞歸  
26.     if (vset[m].size())  
27.     {  
28.         return vset[m];  
29.     }  
30.     for (int i=1; i<=m/2; i++)  
31.         if ((i&m) == i)  
32.         {  
33.             set<Elem>& s1 = Fork(i);  
34.             set<Elem>& s2 = Fork(m-i);  
35.             set<Elem>::iterator cit1;  
36.             set<Elem>::iterator cit2;  
37.             // 得到兩個子集合的笛卡爾積，并對結果集合的元素對進行6種運算  
38.             for (cit1=s1.begin(); cit1!=s1.end(); cit1++)  
39.                 for (cit2=s2.begin(); cit2!=s2.end(); cit2++)  
40.                 {  
41.                     string str;  
42.                     str = "("+cit1->info+"+"+cit2->info+")";  
43.                     vset[m].insert(Elem(cit1->res+cit2->res,str));  
44.                     str = "("+cit1->info+"-"+cit2->info+")";  
45.                     vset[m].insert(Elem(cit1->res-cit2->res,str));  
46.                     str = "("+cit2->info+"-"+cit1->info+")";;  
47.                     vset[m].insert(Elem(cit2->res-cit1->res,str));  
48.                     str = "("+cit1->info+"*"+cit2->info+")";  
49.                     vset[m].insert(Elem(cit1->res*cit2->res,str));  
50.                     if (abs(cit2->res)>EPS)   
51.                     {  
52.                         str = "("+cit1->info+"/"+cit2->info+")";  
53.                         vset[m].insert(Elem(cit1->res/cit2->res,str));  
54.                     }  
55.                     if (abs(cit1->res)>EPS)  
56.                     {  
57.                         str = "("+cit2->info+"/"+cit1->info+")";  
58.                         vset[m].insert(Elem(cit2->res/cit1->res,str));  
59.                     }  
60.                 }  
61.         }  
62.     return vset[m];  
63. }  
64. int main()  
65. {  
66.     int i;  
67.     for (i=0; i<N; i++)  
68.         cin >> A[i];  
69.     // 遞歸的結束條件  
70.     for (i=0; i<N; i++)  
71.     {  
72.         char str[10];  
73.         sprintf(str,"%d",A[i]);  
74.         vset[1<<i].insert(Elem(A[i],str));  
75.     }  
76.     Fork((1<<N)-1);//開始1111 表示四個數   
77.     // 顯示算出24點的運算過程  
78.     set<Elem>::iterator it;  
79.     for (it=vset[(1<<N)-1].begin();   
80.        it!=vset[(1<<N)-1].end(); it++)  
81.         {  
82.             if (abs(it->res-RES) < EPS)  
83.                 cout << it->info << endl;  
84.     }  
85. }  

參考來源: 1. <<程式設計之美>> 2. http://blog.csdn.net/tianshuai11/article/details/7713640