【アルゴリズム29】速算24
47626 ワード
問題の説明
出典:PAT ds 2-08
4つの数字a,b,c,dが与えられ、値範囲は[1,13]である.適切な演算子+、-、*、/、およびカッコ(,)を追加して、式を24に等しくし、可能な式スキームを与えます.不可能な場合は-1を返します.
例えば、入力2,3,12,12,出力(3-2)*12)+12.
入力5,5,5,2,出力-1.
もんだいぶんせき
この問題には良いアルゴリズムがないようで、暴力的に検索するしかない.
まず、与えられたすべての数字を全配列し、合計$A_があります.4^4=24$の配列
次に、各配列について、3つの演算子を追加する必要があります.各演算子には4つの選択肢があり、合計$4*4*4=64$があります.
最後に、得られた式の優先度を変更するためにカッコを付ける方法は、合計5つしかありません. (A @ B)@(C@D); (A@(B@C))@D; ((A@B)@C)@D; A((B@C)@D); A@(B@(C@D));
したがって、可能な限り$24*64*5=7680$の選択肢があります.
サブ関数int calcluateBinaryExpression(int a,int b,char op)を定義して、a op bの値を計算します.主関数はまずdo{}while(next_permutation)を用いてすべての全配列過程を取得し,各配列a,b,c,dについて,各カッコ付け方式についてカッコ付け優先度で式の値を計算し,24に等しいか否かを判断し,等しい場合は直接return,そうでない場合は次のカッコ付け方式を判断する.
注意:op=='/',a/bの場合、bを保証する必要があります!=0 && a % b == 0.この条件を満たさなければ、次のサイクルを直接行います.
プログラムソース
参考文献
[1] 速算24アルゴリズムの考え方
[2] 24 Game/Countdown/Number Game solver, but without parentheses in the answer
出典:PAT ds 2-08
4つの数字a,b,c,dが与えられ、値範囲は[1,13]である.適切な演算子+、-、*、/、およびカッコ(,)を追加して、式を24に等しくし、可能な式スキームを与えます.不可能な場合は-1を返します.
例えば、入力2,3,12,12,出力(3-2)*12)+12.
入力5,5,5,2,出力-1.
もんだいぶんせき
この問題には良いアルゴリズムがないようで、暴力的に検索するしかない.
まず、与えられたすべての数字を全配列し、合計$A_があります.4^4=24$の配列
次に、各配列について、3つの演算子を追加する必要があります.各演算子には4つの選択肢があり、合計$4*4*4=64$があります.
最後に、得られた式の優先度を変更するためにカッコを付ける方法は、合計5つしかありません.
したがって、可能な限り$24*64*5=7680$の選択肢があります.
サブ関数int calcluateBinaryExpression(int a,int b,char op)を定義して、a op bの値を計算します.主関数はまずdo{}while(next_permutation)を用いてすべての全配列過程を取得し,各配列a,b,c,dについて,各カッコ付け方式についてカッコ付け優先度で式の値を計算し,24に等しいか否かを判断し,等しい場合は直接return,そうでない場合は次のカッコ付け方式を判断する.
注意:op=='/',a/bの場合、bを保証する必要があります!=0 && a % b == 0.この条件を満たさなければ、次のサイクルを直接行います.
プログラムソース
1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <algorithm>
5 #include <functional>
6 #include <cstdio>
7 #include <cstdlib>
8 #include <cassert>
9 using namespace std;
10
11 // given number a, b and operator ch, return eval(a ch b)
12 int calculateBinaryExpression(int a, int b, char ch)
13 {
14 switch(ch)
15 {
16 case '+':
17 return a + b;
18 break;
19 case '-':
20 return a - b;
21 break;
22 case '*':
23 return a * b;
24 break;
25 case '/':
26 assert(b != 0);
27 return a / b;
28 break;
29 default:
30 cerr << "WRONG OPERATOR !" << endl;
31 return -1;
32 break;
33 }
34 }
35
36 // Make 24 game
37 // BASIC IDEA: permutation all the possible cases: A(4, 4) = 24;
38 // Need 3 operators: 4 * 4 * 4 = 64;
39 // All five possible adding parenthese:
40 // (1) (A @ B) @ (C @ D)
41 // (2) (A @ (B @ C) ) @ D
42 // (3) ( (A @ B) @ C) @ D
43 // (4) A @ ( ( B @ C) @ D)
44 // (5) A @ ( B @ (C @ D) )
45 // Total Possible cases: 24 * 64 * 5 = 7680, Brute Force
46 // Input: 4 numbers in [1, 13],
47 // use '+','-','*','/' and '(',')' to make 24
48 // Output: If it is possible to make 24, output the expression
49 // Else return -1;
50 // Notice: When calcalute x / y, need to assert (y != 0 && x % y == 0)
51 // If Not, continue
52 string make24(int num1, int num2, int num3, int num4)
53 {
54 vector<int> v(4, 0);
55 v[0] = num1; v[1] = num2; v[2] = num3; v[3] = num4;
56 sort(v.begin(), v.end());
57
58 string ops("+-*/");
59
60 do
61 {
62 // The first parenthesis
63 // (A @ B) @ (C @ D)
64 for (size_t i = 0; i < ops.size(); ++i)
65 {
66 // A @ B
67 char op1 = ops[i];
68 if (op1 == '/' && (v[1] == 0 || v[0] % v[1] != 0)) continue;
69 int ans1 = calculateBinaryExpression(v[0], v[1], op1);
70 for (size_t j = 0; j < ops.size(); ++j)
71 {
72 // C @ D
73 char op2 = ops[j];
74 if (op2 == '/' && (v[3] == 0 || v[2] % v[3] != 0)) continue;
75 int ans2 = calculateBinaryExpression(v[2], v[3], op2);
76
77 for (size_t k = 0; k < ops.size(); ++k)
78 {
79 // (A @ B) @ (C @ D)
80 char op3 = ops[k];
81 if (op3 == '/' && (ans2 == 0 || ans1 % ans2 != 0)) continue;
82 int ans = calculateBinaryExpression(ans1, ans2, op3);
83 if (ans == 24)
84 {
85 string str;
86 str.push_back('(');
87 str += to_string((long long)(v[0]));
88 str.push_back(op1);
89 str += to_string((long long)(v[1]));
90 str.push_back(')');
91 str.push_back(op3);
92 str.push_back('(');
93 str += to_string((long long)(v[2]));
94 str.push_back(op2);
95 str += to_string((long long)(v[3]));
96 str.push_back(')');
97 return str;
98 }
99 }
100 }
101
102 }
103
104 // The second parethesis
105 // (A op2 (B op1 C)) op3 D
106 for (size_t i = 0; i < ops.size(); ++i)
107 {
108 char op1 = ops[i];
109 if (op1 == '/' && (v[2] == 0 || v[1] % v[2] != 0)) continue;
110 int ans1 = calculateBinaryExpression(v[1], v[2], op1);
111 for (size_t j = 0; j < ops.size(); ++j)
112 {
113 char op2 = ops[j];
114 if (op2 == '/' && (ans1 == 0 || v[0] % ans1 != 0)) continue;
115 int ans2 = calculateBinaryExpression(v[0], ans1, op2);
116 for (size_t k = 0; k < ops.size(); ++k)
117 {
118 char op3 = ops[k];
119 if (op3 == '/' && (v[3] == 0 || ans2 % v[3] != 0)) continue;
120 int ans = calculateBinaryExpression(ans2, v[3], op3);
121 if (ans == 24)
122 {
123 string str;
124 str.push_back('(');
125 str += to_string((long long)v[0]);
126 str.push_back(op2);
127 str.push_back('(');
128 str += to_string((long long)v[1]);
129 str.push_back(op1);
130 str += to_string((long long)v[2]);
131 str.push_back(')');
132 str.push_back(')');
133 str.push_back(op3);
134 str += to_string((long long)v[3]);
135 return str;
136 }
137 }
138 }
139 }
140
141 // The third parentheses
142 // ( ( A op1 B) op2 C) op3 D
143 for (size_t i = 0; i < ops.size(); ++i)
144 {
145 char op1 = ops[i];
146 if (op1 == '/' && (v[1] == 0 || v[0] % v[1] != 0)) continue;
147 int ans1 = calculateBinaryExpression(v[0], v[1], op1);
148 for (size_t j = 0; j < ops.size(); ++j)
149 {
150 char op2 = ops[j];
151 if (op2 == '/' && (v[2] == 0 || ans1 % v[2] != 0)) continue;
152 int ans2 = calculateBinaryExpression(ans1, v[2], op2);
153 for (size_t k = 0; k < ops.size(); ++k)
154 {
155 char op3 = ops[k];
156 if (op3 == '/' && (v[3] == 0 || ans2 % v[3] != 0)) continue;
157 int ans = calculateBinaryExpression(ans2, v[3], op3);
158 if (ans == 24)
159 {
160 string str("((");
161 str += to_string((long long)v[0]);
162 str.push_back(op1);
163 str += to_string((long long)v[1]);
164 str.push_back(')');
165 str.push_back(op2);
166 str += to_string((long long)v[2]);
167 str.push_back(')');
168 str.push_back(op3);
169 str += to_string((long long)v[4]);
170 return str;
171 }
172 }
173 }
174 }
175
176 // The fourth parentheses
177 // A op3 ( ( B op1 C ) op2 D)
178 for (size_t i = 0; i < ops.size(); ++i)
179 {
180 char op1 = ops[i];
181 if (op1 == '/' && (v[2] == 0 || v[1] % v[2] != 0)) continue;
182 int ans1 = calculateBinaryExpression(v[1], v[2], op1);
183 for (size_t j = 0; j < ops.size(); ++j)
184 {
185 char op2 = ops[j];
186 if (op2 == '/' && (v[3] == 0 || ans1 % v[3] != 0)) continue;
187 int ans2 = calculateBinaryExpression(ans1, v[3], op2);
188 for (size_t k = 0; k < ops.size(); ++k)
189 {
190 char op3 = ops[k];
191 if (op3 == '/' && (ans2 == 0 || v[0] % ans2 != 0)) continue;
192 int ans = calculateBinaryExpression(v[0], ans2, op3);
193 if (ans == 24)
194 {
195 string str;
196 str += to_string((long long)v[0]);
197 str.push_back(op3);
198 str += "((";
199 str += to_string((long long)v[1]);
200 str.push_back(op1);
201 str += to_string((long long)v[2]);
202 str.push_back(')');
203 str.push_back(op2);
204 str += to_string((long long)v[3]);
205 str.push_back(')');
206 return str;
207 }
208 }
209 }
210 }
211
212 // The fifth parenthese
213 // A op3 ( B op2 ( C op1 D) );
214 for (size_t i = 0; i < ops.size(); ++i)
215 {
216 char op1 = ops[i];
217 if (op1 == '/' && (v[3] == 0 || v[2] % v[3] != 0)) continue;
218 int ans1 = calculateBinaryExpression(v[2], v[3], op1);
219 for (size_t j = 0; j < ops.size(); ++j)
220 {
221 char op2 = ops[j];
222 if (op2 == '/' && (ans1 == 0 || v[1] % ans1 != 0)) continue;
223 int ans2 = calculateBinaryExpression(v[1], ans1, op2);
224 for (size_t k = 0; k < ops.size(); ++k)
225 {
226 char op3 = ops[k];
227 if (op3 == '/' && (ans2 == 0 || v[0] % ans2 != 0)) continue;
228 int ans = calculateBinaryExpression(v[0], ans2, op3);
229 if (ans == 24)
230 {
231 string str;
232 str += to_string((long long)v[0]);
233 str.push_back(op3);
234 str.push_back('(');
235 str += to_string((long long)v[1]);
236 str.push_back(op2);
237 str.push_back('(');
238 str += to_string((long long)v[2]);
239 str.push_back(op1);
240 str += to_string((long long)v[3]);
241 str += "))";
242 return str;
243 }
244 }
245 }
246 }
247
248 } while(next_permutation(v.begin(), v.end()));
249
250 return "-1";
251 }
252
253 int main()
254 {
255 int a, b, c, d;
256 cin >> a >> b >> c >> d;
257 string ans = make24(a, b, c, d);
258 cout << ans << endl;
259 return 0;
260 }参考文献
[1] 速算24アルゴリズムの考え方
[2] 24 Game/Countdown/Number Game solver, but without parentheses in the answer