首页 > 代码库 > 【算法29】速算24
【算法29】速算24
问题描述
题目来源：PAT ds 2-08
给定四个数字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$中排列方式；
然后对于每一种排列方式，需要添加三个运算符，每个运算符有加减乘除四种选择，总共有$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 #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 parethesis105 // (A op2 (B op1 C)) op3 D106 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 parentheses142 // ( ( A op1 B) op2 C) op3 D143 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 parentheses177 // 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 parenthese213 // 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
【算法29】速算24
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。