该题与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;
}



京公网安备 11010502036488号