欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

24点问题

程序员文章站 2022-03-31 20:44:13
...

CSDN编程挑战里的题目

24点游戏是一种使用扑克牌来进行的益智类游戏,游戏内容是:
从一副扑克牌中抽去大小王剩下52张,任意抽取4张牌,把牌面
上的数(A代表1)运用加、减、乘、除和括号进行运算得出24。
每张牌都必须使用一次,但不能重复使用。 有些组合有不同种
算法,例如要用2,4,6,12四张牌组合成24点,可以有如下几
种组合方法:
2 + 4 + 6 + 12 = 24
4 × 6 ÷ 2 + 12 = 24
12 ÷ 4 × (6 + 2) = 24
当然,也有些组合算不出24,如1、1、1、1 和 6、7、8、8等组合.

我的思路是穷举法,将四个数的所有可能运算方式都处理一遍,如果有24则正确.可惜提交了三次才正确,没有获奖的机会了.

我的程序还可以输出其运算的表达式.

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include <string>
  4 
  5 #include <cmath>
  6 #include <cfloat>
  7 #include <cstring>
  8 #include <cstdio>
  9 
 10 // 4张牌的排列组合
 11 const int g_fourlist[24][4] = 
 12 {
 13     {0,1,2,3},
 14     {0,1,3,2},
 15     {0,2,1,3},
 16     {0,2,3,1},
 17     {0,3,2,1},
 18     {0,3,1,2},
 19 
 20     {1,2,3,0},
 21     {1,2,0,3},
 22     {1,3,2,0},
 23     {1,3,0,2},
 24     {1,0,2,3},
 25     {1,0,3,2},
 26 
 27     {2,1,3,0},
 28     {2,1,0,3},
 29     {2,3,1,0},
 30     {2,3,0,1},
 31     {2,0,1,3},
 32     {2,0,3,1},
 33 
 34     {3,1,2,0},
 35     {3,1,0,2},
 36     {3,2,1,0},
 37     {3,2,0,1},
 38     {3,0,1,2},
 39     {3,0,2,1},
 40 };
 41 
 42 void _buildExpress(int a, int b, int c, int d, int n, int i, int j, int k, char* szExpress)
 43 {
 44     char szN[2] = {0};
 45     char szI[2] = {0};
 46     char szJ[2] = {0};
 47     char szK[2] = {0};
 48 
 49     if (n&1)
 50     {
 51         szN[0] = '-';
 52     }
 53 
 54     switch (i)
 55     {
 56     case 0:
 57         szI[0] = '+';
 58         break;
 59     case 1:
 60         szI[0] = '-';
 61         break;
 62     case 2:
 63         szI[0] = '*';
 64         break;
 65     case 3:
 66         szI[0] = '/';
 67         break;
 68     }
 69 
 70     switch (j)
 71     {
 72     case 0:
 73         szJ[0] = '+';
 74         break;
 75     case 1:
 76         szJ[0] = '-';
 77         break;
 78     case 2:
 79         szJ[0] = '*';
 80         break;
 81     case 3:
 82         szJ[0] = '/';
 83         break;
 84     }
 85 
 86     switch (k)
 87     {
 88     case 0:
 89         szK[0] = '+';
 90         break;
 91     case 1:
 92         szK[0] = '-';
 93         break;
 94     case 2:
 95         szK[0] = '*';
 96         break;
 97     case 3:
 98         szK[0] = '/';
 99         break;
100     }
101 
102     if (n&2)
103     {
104         sprintf(szExpress, "%s%d %s %d %s (%d %s %d) == 24", szN, a, szI, b, szJ, c, szK, d);
105     }
106     else
107     {
108         sprintf(szExpress, "%s%d %s %d %s %d %s %d == 24", szN, a, szI, b, szJ, c, szK, d);
109     }
110 }
111 
112 /*
113 表达式的组合有以下四类:
114 a?b?c?d
115 (-a)?b?c?d)
116 (a?b) ? (c?d)
117 ((-a)?b) ? (c?d))
118 表达式从左向右计算,
119 +,-,*,/无优先级顺序
120 
121 6/(1-(3/4))
122 */
123 
124 bool _can24(int a, int b, int c, int d, char* szExpress)
125 {
126     float valueA;
127     float valueAB;
128     float valueABC;
129     float valueCD;
130     float valueABCD;
131 
132     for (int n = 0; n < 4; n++)
133     {
134         valueA = (n&1) ? -(float)a : (float)a;
135 
136         for (int i = 0; i < 4; i++)
137         {
138             switch (i)
139             {
140             case 0:
141                 valueAB = valueA+b;
142                 break;
143             case 1:
144                 valueAB = valueA-b;
145                 break;
146             case 2:
147                 valueAB = valueA*b;
148                 break;
149             case 3:
150                 valueAB = valueA/b;
151                 break;
152             }
153 
154             if (n&2)
155             {
156                 // (a?b) ? (c?d)
157                 for (int k = 0; k < 4; k++)
158                 {
159                     switch (k)
160                     {
161                     case 0:
162                         valueCD = (float)c+d;
163                         break;
164                     case 1:
165                         valueCD = (float)c-d;
166                         break;
167                     case 2:
168                         valueCD = (float)c*d;
169                         break;
170                     case 3:
171                         valueCD = (float)c/d;
172                         break;
173                     }
174 
175                     for (int j = 0; j < 4; j++)
176                     {
177                         switch (j)
178                         {
179                         case 0:
180                             valueABCD = valueAB+valueCD;
181                             break;
182                         case 1:
183                             valueABCD = valueAB-valueCD;
184                             break;
185                         case 2:
186                             valueABCD = valueAB*valueCD;
187                             break;
188                         case 3:
189                             valueABCD = valueAB/valueCD;
190                             break;
191                         }
192 
193                         if (fabs(valueABCD - 24) < FLT_EPSILON)
194                         {
195                             if (szExpress)
196                             {
197                                 _buildExpress(a, b, c, d, n, i, j, k, szExpress);
198                             }
199                             return true;
200                         }
201                     }
202                 }
203             }
204             else
205             {
206                 for (int j = 0; j < 4; j++)
207                 {
208                     switch (j)
209                     {
210                     case 0:
211                         valueABC = valueAB+c;
212                         break;
213                     case 1:
214                         valueABC = valueAB-c;
215                         break;
216                     case 2:
217                         valueABC = valueAB*c;
218                         break;
219                     case 3:
220                         valueABC = valueAB/c;
221                         break;
222                     }
223 
224                     for (int k = 0; k < 4; k++)
225                     {
226                         switch (k)
227                         {
228                         case 0:
229                             valueABCD = valueABC+d;
230                             break;
231                         case 1:
232                             valueABCD = valueABC-d;
233                             break;
234                         case 2:
235                             valueABCD = valueABC*d;
236                             break;
237                         case 3:
238                             valueABCD = valueABC/d;
239                             break;
240                         }
241 
242                         if (fabs(valueABCD - 24) < FLT_EPSILON)
243                         {
244                             if (szExpress)
245                             {
246                                 _buildExpress(a, b, c, d, n, i, j, k, szExpress);
247                             }
248                             return true;
249                         }
250                         else if (fabs(valueABCD - 1.0f/24) < FLT_EPSILON)
251                         {
252                             // 1/24也可以
253                             if (szExpress)
254                             {
255                                 _buildExpress(a, b, c, d, n, i, j, k, szExpress);
256                             }
257                             return true;
258                         }
259                     }
260                 }
261             }
262         }
263     }
264 
265     return false;
266 }
267 
268 bool Can24(const int four[4], char* szExpress)
269 {
270     for (int i = 0; i < 24; i++)
271     {
272         if (_can24(four[g_fourlist[i][0]], 
273                    four[g_fourlist[i][1]],
274                    four[g_fourlist[i][2]],
275                    four[g_fourlist[i][3]],
276                    szExpress))
277         {
278             return true;
279         }
280     }
281 
282     return false;
283 }

 

 

转载于:https://my.oschina.net/abcijkxyz/blog/722592

上一篇: 24点问题

下一篇: 坦克游戏制作