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