该题与ACM. HJ67 24点游戏算法 & 679. 24 点游戏类似,但是又存在差异。
比如输出结果的运算是不存在括号的,所以没有运算符的优先级,都是从左往右进行运算,并且需要输出运算过程。
为此,我们可以使用暴力遍历进行查找,数字 num 的组合有4 * 3 * 2 * 1 = 24 种,运算符 op 的组合有 4 * 4 * 4 = 64 种,因此具有24 * 64 = 1536 种组合,我们可以用循环进行遍历。
#include <iostream> #include <string> #include <vector> using namespace std; const int TARGET = 24; string convert(int num){ // 将数字转换为字符串 if(num >= 2 && num <= 10) return to_string(num); if(num == 1) return "A"; if(num == 11) return "J"; if(num == 12) return "Q"; if(num == 13) return "K"; return to_string(num); } string convertOP(int num){ // 将数字转换为运算符字符串 if(num == 1) return "+"; if(num == 2) return "-"; if(num == 3) return "*"; if(num == 4) return "/"; return "NULL"; } int cal(int a, int op, int b){ // 两数计算 if(op == 1) return a + b; if(op == 2) return a - b; if(op == 3) return a * b; if(op == 4) return a / b; return 1; } string getStr(int a, int op1, int b, int op2, int c, int op3, int d){ // 最终结果转换 return convert(a) + convertOP(op1) + convert(b) + convertOP(op2) + convert(c) + convertOP(op3) + convert(d); } string traversal(vector<int> & nums){ for (int i = 0; i < 4; i++){ // nums0 for(int j = 0; j < 4; ++j){ // nums1 if(j == i) continue; for(int k = 0; k < 4; ++k){ // nums2 if(k == i || k == j) continue; for(int l = 0; l < 4; ++l){ // nums3 if(l == i || l == j || l ==k) continue; for(int op1 = 1; op1 <= 4; ++op1){ // op1 for(int op2 = 1; op2 <= 4; ++op2){ // op2 for(int op3 = 1; op3 <= 4; ++op3){ // op3 int sum = cal(nums[i], op1, nums[j]); sum = cal(sum, op2, nums[k]); sum = cal(sum, op3, nums[l]); if(sum == TARGET) return getStr(nums[i], op1, nums[j], op2, nums[k], op3, nums[l]); } } } } } } } return "NONE"; } int main(){ string strs[4]; vector<int> nums(4, 0); while(cin >> strs[0] >> strs[1] >> strs[2] >> strs[3]){ for(int i = 0; i < 4; ++i){ if(strs[i][0] >= '2' && strs[i][0] <= '9'){ nums[i] = strs[i][0] - '0'; }else if(strs[i][0] == 'A'){ nums[i] = 1; }else if(strs[i][0] == 'J'){ nums[i] = 11; }else if(strs[i][0] == 'Q'){ nums[i] = 12; }else if(strs[i][0] == 'K'){ nums[i] = 13; }else if(strs[i][0] == '1'){ nums[i] = 10; }else{ cout << "ERROR"; return 0; } } cout << traversal(nums) << endl; } return 0; }