题解 | #24点运算#
24点运算
http://www.nowcoder.com/practice/7e124483271e4c979a82eb2956544f9d
题目的主要信息：
完成24点运算，输入四个数字，找到合适的运算顺序，使得结果为24。需要注意以下几点：
- 如果有大小王输出ERROR表示无法计算。
- 仅使用+、-、*、/ 四种运算。
- 最后如果没有找到运算顺序，则输出NONE。
方法一：暴力递归
首先将给定的四个数字提取出来，如果有JQKA则转换为数字。如果有joker或者JOKER则输出ERROR。然后对四个数字的所有排列枚举一遍，每个排列都判断是否能完成24点计算，如果能，则结束循环，输出运算。判断是否能完成24点也是用暴力枚举的方式，首先枚举第一个运算符，然后再枚举第二个运算符，枚举第三个运算符，如果当前运算符的选择可以的到结果24则结束递归。输出的时候需要注意把11、12、13、1数字转为J、Q、K、A。
#include <bits/stdc++.h>
using namespace std;
map<char, int> mp;
bool get(int a, int b, char& op1) {//穷举最后一个符号
if (a + b == 24) {
op1 = '+';
return true;
}
if (a - b == 24) {
op1 = '-';
return true;
}
if (a * b == 24) {
op1 = '*';
return true;
}
if (a / b == 24) {
op1 = '/';
return true;
}
return false;
}
bool get(int a, int b, int c, char& op1, char& op2) {//穷举第二个运算符
if (get(a + b, c, op2)) {
op1 = '+';
return true;
}
if (get(a - b, c, op2)) {
op1 = '-';
return true;
}
if (get(a * b, c, op2)) {
op1 = '*';
return true;
}
if (get(a / b, c, op2)) {
op1 = '/';
return true;
}
return false;
}
bool get(int a, int b, int c, int d, char& op1, char& op2, char& op3) {//穷举第一个符号
//+ - * /每一种方法都穷举一遍，递归计算
if (get(a + b, c, d, op2, op3)) {
op1 = '+';
return true;
}
if (get(a - b, c, d, op2, op3)) {
op1 = '-';
return true;
}
if (get(a * b, c, d, op2, op3)) {
op1 = '*';
return true;
}
if (get(a / b, c, d, op2, op3)) {
op1 = '/';
return true;
}
return false;
}
int main() {
string s;
mp['J'] = 11, mp['Q'] = 12, mp['K'] = 13, mp['A'] = 1;
map<int, char> mp2;
mp2[11] = 'J', mp2[12] = 'Q', mp2[13] = 'K', mp2[1] = 'A';
while (getline(cin, s)) {
if (s.find("joker") != s.npos || s.find("JOKER") != s.npos) {//包含大小王无法进行计算，输出ERROR
cout << "ERROR" << endl;
continue;
}
stringstream ss(s);
string tmp;
vector<int> num;
while (getline(ss, tmp, ' ')) {//用空格切割获得四个数字
if (!mp[tmp[0]]){//如果不是JQKA 则直接转为数字
num.push_back(stoi(tmp));
}else{//否则用mp映射到数字
num.push_back(mp[tmp[0]]);
}
}
sort(num.begin(), num.end());
bool flag = false;
char op[3];
do {
if (get(num[0], num[1], num[2], num[3], op[0], op[1], op[2])) {//如果这个排列可以完成24点运算
if (mp2[num[0]]){//输出第一个数字，如果是11 12 13 1转换为J Q K A后再输出
cout << mp2[num[0]];
}else{
cout<<num[0];
}
for (int i = 1; i < 4; i++) {
cout << op[i - 1];//输出运算符
if (mp2[num[i]]){
cout << mp2[num[i]];
}else{
cout << num[i];
}
}
cout << "\n";
flag = true;//找了一种解法，flag为true
break;
}
} while (next_permutation(num.begin(), num.end()));//每个排列都遍历一遍
if (!flag){
//没有找到解法
cout << "NONE" << endl;
}
}
}
复杂度分析：
- 时间复杂度：，虽然过程繁琐，但是说到底是对4个数的运算进行枚举，只需要常数时间。
- 空间复杂度：，因为是对4个数进行运算，递归栈的大小是常数。
方法二：枚举
方法一中我们枚举了所有操作数可能的顺序，同样的，我们也可以对运算符进行枚举。最终我们只需在三个地方用到运算符，每个地方运算符都可能是中的一种，总共有4x4x4种可能，我们枚举所有操作数的顺序和运算符的64种可能，计算当前操作数顺序和运算符顺序下的结果，如果结果为24，则结束枚举，输出运算过程。运算符的64种顺序枚举用三个for循环实现，calculator函数计算当前操作数顺序和运算符的结果。
具体做法：
#include <bits/stdc++.h>
using namespace std;
map<char, int> mp;
vector<char> op={'+', '-', '*', '/'};
vector<char> operation;//当前的运算符顺序
int calculator(vector<int> num, vector<char> operation) {//计算当前顺序的操作数和运算符的结果
int sum=num[0];
for(int i=0,j=1;i<operation.size();i++,j++){
switch(operation[i]){
case '+':
sum += num[j];
break;
case '-':
sum -= num[j];
break;
case '*':
sum *= num[j];
break;
case '/':
sum /= num[j];
break;
}
}
return sum;
}
bool dfs(int a, int b, int c, int d) {
vector<int> num = {a, b, c, d};
for(int i=0;i<op.size();i++){//三个循环枚举所有的操作符顺序可能
for(int j=0;j<op.size();j++){
for(int k=0;k<op.size();k++){
operation = {op[i], op[j], op[k]};//枚举所有可能的运算符顺序
int sum = calculator(num, operation);//计算结果
if(sum == 24){//若结果为24则结束枚举
return true;
}
}
}
}
return false;
}
int main() {
string s;
mp['J'] = 11, mp['Q'] = 12, mp['K'] = 13, mp['A'] = 1;
map<int, char> mp2;
mp2[11] = 'J', mp2[12] = 'Q', mp2[13] = 'K', mp2[1] = 'A';
while (getline(cin, s)) {
if (s.find("joker") != s.npos || s.find("JOKER") != s.npos) {//包含大小王无法进行计算，输出ERROR
cout << "ERROR" << endl;
continue;
}
stringstream ss(s);
string tmp;
vector<int> num;
while (getline(ss, tmp, ' ')) {//用空格切割获得四个数字
if (!mp[tmp[0]]){//如果不是JQKA 则直接转为数字
num.push_back(stoi(tmp));
}else{//否则用mp映射到数字
num.push_back(mp[tmp[0]]);
}
}
sort(num.begin(), num.end());
bool flag = false;
char op[3];
do {
if (dfs(num[0], num[1], num[2], num[3])) {//如果这个操作数排列可以完成24点运算
if (mp2[num[0]]){//输出第一个数字，如果是11 12 13 1转换为J Q K A后再输出
cout << mp2[num[0]];
}else{
cout<<num[0];
}
for (int i = 1; i < 4; i++) {
cout << operation[i - 1];//输出运算符
if (mp2[num[i]]){
cout << mp2[num[i]];
}else{
cout << num[i];
}
}
cout << "\n";
flag = true;//找了一种解法，flag为true
break;
}
} while (next_permutation(num.begin(), num.end()));//每个排列都遍历一遍
if (!flag){
//没有找到解法
cout << "NONE" << endl;
}
}
}
复杂度分析：
- 时间复杂度：，虽然有三个for循环，但是总共只有64种可能，只需要常数时间。
- 空间复杂度：，只用了常数空间。
