题解 | #24点运算#

24点运算

http://www.nowcoder.com/practice/7e124483271e4c979a82eb2956544f9d

题意

给4张扑克牌，如果非法输出ERROR，否者找一个运算让运算结果为24，没有方案输出NONE

限制：只有加减乘和整除，但是优先级相同（也就是从左向右计算），没有括号和其它

方法

枚举值和符号

分成几个步骤

字符串转数值，其中joker/JOKER 为-1
判断是否有 joker/JOKER 有则输出ERROR
递归枚举值的排列
递归枚举符号的排列
对每种情况进行运算，如果得到24则输出方案

以题目中样例数据4 2 K A为例

alt

代码

#include<bits/stdc++.h>
using namespace std;
char s[4][10];

// 3 4 5 6 7 8 9 10 J  Q  K  A 2 joker JOKER
// 3 4 5 6 7 8 9 10 11 12 13 1 2 -1    -1
int s2int(const char * s,int n){ // 字符串转值
    if(n == 2)return 7; // 10
    if(n == 5)return -1;// joker / JOKER
    if(s[0] == 'A')return 1;
    if(s[0] == 'K')return 13;
    if(s[0] == 'Q')return 12;
    if(s[0] == 'J')return 11;
    return s[0]-'0'; // 2~9
}
const int INF = 0x3f3f3f3f; // 无限大
int calc(int v0,char ch,int v1) { // 运算
    if(ch == '+')return v0+v1;
    if(ch == '-')return v0-v1;
    if(ch == '*')return v0*v1;
    if(ch == '/')return v1 == 0?INF:v0/v1; // 除0
    return INF;
}

// 选中的下标 和 运算符
bool dfs(vector<int>&arr,vector<int> & v,vector<char> &op){ // 枚举所有状态
    const char ch[] = {'+','-','*','/'};
    if(v.size() == 4){
        if(op.size() == 3){
            int r = arr[v[0]];
            for(int i=0;i<3;i++){
                r = calc(r,op[i],arr[v[i+1]]);
                if(r == INF)return false; // 除零
            }
            if(r == 24){
                printf("%s",s[v[0]]);
                for(int i = 0;i< 3;i++){
                    printf("%c%s",op[i],s[v[i+1]]);
                }
                printf("\n");
            }
            return r == 24; // 是否24点
        }
        for(int i = 0;i<4;i++){ // 枚举符号
            op.push_back(ch[i]);
            bool r = dfs(arr,v,op); // 递归
            op.pop_back();
            if(r) return true;
        }
        return false;
    }
    for(int i = 0 ;i < 4;i++){ // 枚举数值
        bool exist = false;
        for(auto idx : v){ // 要使用未使用过的
            if(idx == i)exist = true;
        }
        if(exist)continue;
        v.push_back(i);
        bool r = dfs(arr,v,op); // 递归
        v.pop_back();
        if(r) return r;
    }
    return false;
}

void work(vector<int>&arr){
    for(int i = 0;i<4;i++) {
        if(arr[i] == -1){ // 存在joker，输出ERROR 
            printf("ERROR\n");
            return ;
        }
    }
    vector<int> v;
    vector<char> op;
    bool r = dfs(arr,v,op);
    if(!r)printf("NONE\n");
}

int main(){
    vector<int> arr;
    for(int i = 0;i < 4;i++){
        scanf("%s",s+i);
        arr.push_back(s2int(s[i],strlen(s[i])));  // 读入并转换成数字
    }
    work(arr);
    return 0;
}

复杂度分析

时间复杂度: 因为所有状态都被枚举了，所以计算的复杂度为，数值的排列和符号的枚举，为 $O (4^{n})$ , 但是因为n比较小只有7，所以可以在时间复杂度内完成

空间复杂度: 主要消耗在递归层级，和中间变量上，不超过数值符号总个数，所以复杂度为 $O (n)$

递归同时计算

一般来说，递归搜索更好的是能伴随着运算，而不是到了端点才运算，但是这道题保证了除法的合法性，所以我们其实无枝可剪

但是通过把符号和运算符变成一次操作，可以简化递归层级的传递过程

代码

#include<bits/stdc++.h>
using namespace std;
char s[4][10];

// 3 4 5 6 7 8 9 10 J  Q  K  A 2 joker JOKER
// 3 4 5 6 7 8 9 10 11 12 13 1 2 -1    -1
int s2int(const char * s,int n){ // 字符串转值
    if(n == 2)return 7; // 10
    if(n == 5)return -1;// joker / JOKER
    if(s[0] == 'A')return 1;
    if(s[0] == 'K')return 13;
    if(s[0] == 'Q')return 12;
    if(s[0] == 'J')return 11;
    return s[0]-'0'; // 2~9
}

int calc(int v0,char ch,int v1) { // 运算
    if(ch == '+')return v0+v1;
    if(ch == '-')return v0-v1;
    if(ch == '*')return v0*v1;
    if(ch == '/')return v0/v1; // 题目保证无 0
    return 0;
}

// 选中的下标 ,运算符,当前运算结果
bool dfs(vector<int>&arr,vector<int> & v,vector<char> &op,int val = 0){ // 枚举所有状态
    const char ch[] = {'+','-','*','/'};
    if(v.size() == 4){
        if( val == 24 ){
            printf("%s",s[v[0]]);
            for(int i = 0;i< 3;i++) {
                printf("%c%s",op[i],s[v[i+1]]);
            }
            printf("\n");
        }
        return val == 24;
    }
    if(v.size() == 0){ // 首个
        for(int i = 0;i < 4;i++){
            v.push_back(i);
            bool r = dfs(arr,v,op,arr[i]);
            v.pop_back();
            if(r) return r;
        }
        return false;
    }
    for(int i = 0 ;i < 4;i++){ // 枚举 数字
        bool exist = false;
        for(auto idx : v){ // 要使用未使用过的
            if(idx == i)exist = true;
        }
        if(exist)continue;
        for(int j = 0; j < 4; j++){ // 枚举运算符
            op.push_back(ch[j]);
            v.push_back(i);
            bool r = dfs(arr,v,op, calc(val,ch[j],arr[i]));
            v.pop_back();
            op.pop_back();
            if(r) return r;
        }
    }
    return false;
}

void work(vector<int>&arr){
    for(int i = 0;i<4;i++) {
        if(arr[i] == -1){ // 存在joker，输出ERROR 
            printf("ERROR\n");
            return ;
        }
    }
    vector<int> v;
    vector<char> op;
    bool r = dfs(arr,v,op);
    if(!r)printf("NONE\n");
}

int main(){
    vector<int> arr;
    for(int i = 0;i < 4;i++){
        scanf("%s",s+i);
        arr.push_back(s2int(s[i],strlen(s[i])));  // 读入并转换成数字
    }
    work(arr);
    return 0;
}