24点运算

作者: 零岁的我 | 来源:发表于2020-05-21 15:26 被阅读0次

题目描述
计算24点是一种扑克牌益智游戏，随机抽出4张扑克牌，通过加(+)，减(-)，乘(*), 除(/)四种运算法则计算得到整数24，本问题中，扑克牌通过如下字符或者字符串表示，其中，小写joker表示小王，大写JOKER表示大王：
3 4 5 6 7 8 9 10 J Q K A 2 joker JOKER
本程序要求实现：输入4张牌，输出一个算式，算式的结果为24点。
详细说明：

运算只考虑加减乘除运算，没有阶乘等特殊运算符号，友情提醒，整数除法要当心；
牌面2_{10对应的权值为2}10, J、Q、K、A权值分别为为11、12、13、1；
输入4张牌为字符串形式，以一个空格隔开，首尾无空格；如果输入的4张牌中包含大小王，则输出字符串“ERROR”，表示无法运算；
输出的算式格式为4张牌通过+-*/四个运算符相连，中间无空格，4张牌出现顺序任意，只要结果正确；
输出算式的运算顺序从左至右，不包含括号，如1+2+3*4的结果为24
如果存在多种算式都能计算得出24，只需输出一种即可，如果无法得出24，则输出“NONE”表示无解。

输入描述: 输入4张牌为字符串形式，以一个空格隔开，首尾无空格；
输出描述: 如果输入的4张牌中包含大小王，则输出字符串“ERROR”，表示无法运算。
因为这里不考虑括号并且只考虑自左向右的运算顺序，所以比较简单。

#include<iostream>
#include<string>
#include<array>
#include<algorithm>
#include<map>

using namespace std;
bool flag = true;

void display(array<float,4> arr)
{
    for(auto value:arr){
        cout<<value<<" ";
    }
    cout<<endl;
}

float compute(float a,float b,int op)
{
    switch(op){
        case 0: return a+b;
        case 1: return a-b;
        case 2: return a*b;
        case 3: 
            if(b==0){
                flag = false;
                return -1;
            }
            else{
                return a/b;
            }
    }
    return 0;
}

string get_op(int op)
{
    switch(op){
        case 0: return "+";
        case 1: return "-";
        case 2: return "*";
        case 3: return "/";
    }
    return " ";
}

string check(array<float,4> arr)
{
    map<int,string> poker={{1,"A"},{2,"2"},{3,"3"},{4,"4"},{5,"5"},{6,"6"},{7,"7"},{8,"8"},{9,"9"},{10,"10"},{11,"J"},{12,"Q"},{13,"K"}};
    int op1,op2,op3;
    string expression="";
    for(int i=0;i<64;++i){
        op1= i%4;
        op2= i/4%4;
        op3=i/16;
        expression = "";
        flag=true; //标志除数是否为0
        //这里只考虑自左向右的顺序计算，并且不考虑符号优先级，如果考虑符号优先级需要使用括号
        if(flag && compute(compute(compute(arr[0],arr[1],op1),arr[2],op2),arr[3],op3)==24 ){
            expression = poker[static_cast<int>(arr[0])] + get_op(op1) + poker[static_cast<int>(arr[1])] + get_op(op2) + poker[static_cast<int>(arr[2])] + get_op(op3) + poker[static_cast<int>(arr[3])];
            return expression;
        }
    }
    return expression;
}

string getPermutation(array<float,4> arr)
{
    sort(arr.begin(),arr.end()); //next_permutation()可以获得基于字典序的全排列，要获得完整的全排列，需要序列初始初始情况下是递增排序的
    string exp = "";
    do{
        exp=check(arr);
        if(exp != "") return exp;
    }while(next_permutation(arr.begin(),arr.end()));
    return exp;
}

int main(int argc,char **argv)
{
    string s=" A234567891JQK"; //可输入合法字符，注意第一个位置是空格，这样可以将其他位置字符对应的数值就是其在字符串中的位置
    bool inputErr=false; //标志是否输入非法字符，即不在s中的字符
    array<float,4> poker;
    for(int i=0;i<4;++i){
        string temp;
        cin>>temp;
        if(temp=="10") poker[i] = stof(temp);
        else if(s.find(temp)!=10 && s.find(temp)!=string::npos){
            poker[i] = s.find(temp);
        }
        else{
            inputErr = true;
        }
    }
    if(inputErr){
        cout<<"ERROR"<<endl;
        return 0;
    }
    string exp=getPermutation(poker);
    if(exp == ""){
        cout<<"NONE"<<endl;
        return 0;
    }
    cout<<exp<<endl;
    return 0 ;
}

运行结果截图

下面是参考别人代码复现的24点游戏，不是对上题的解答。
具体思路请参考：https://blog.csdn.net/octopusflying/article/details/51428337

#include<iostream>
#include<array>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
using namespace std;

bool flag; //标识运算过程中是否出错，除数是否为0

void display(const array<float,4> arr)
{
    for(auto data:arr){
        cout<<data<<" ";
    }
    cout<<endl;
}

//执行加减乘除运算，包括  反减和反除
float compute(float a,float b,int op)
{
    switch(op){
        case 0:
            return a+b;
            break;
        case 1:
            return a-b;
            break;
        case 2:
            return a*b;
            break;
        case 3:
            if(b==0){
                flag = false;
                return -1;
            }else{
                return a/b;
            }
            break;
        case 4:
            return b-a;
            break;
        case 5:
            if(a==0){
                flag=false;
                return -1;
            }else{
                return b/a;
            }
            break;
    }
}

//以字符形式输出结果等于24的表达式1，这里直接暴力的，可能会有更巧妙的方法？
string getExpression1(array<float,4> const arr,array<int,3> const opArr)
{
    string expression= "((" + to_string(arr[0]);
    for(int i=0;i<3;++i){
        switch(opArr[i]){
            case 0: expression += '+' + to_string(arr[i+1]) ; break;
            case 1: expression += '-' + to_string(arr[i+1]) ; break;
            case 2: expression += '*' + to_string(arr[i+1]) ; break;
            case 3: expression += '/' + to_string(arr[i+1]) ; break;
            case 4: 
                if(i==0) 
                {
                    expression = expression.substr(2);
                    expression = "((" + to_string(arr[i+1]) + '-' + expression ; break;
                }
                if(i==1){
                    expression = expression.substr(1);
                    expression = "(" + to_string(arr[i+1]) + '-' + expression ; break;
                }
                else{
                    expression = to_string(arr[i+1]) + '-' + expression ; break;
                }
            case 5: 
                if(i==0) 
                {
                    expression = expression.substr(2);
                    expression = "((" + to_string(arr[i+1]) + '/' + expression ; break;
                }
                if(i==1){
                    expression = expression.substr(1);
                    expression = "(" + to_string(arr[i+1]) + '/' + expression ; break;
                }
                else{
                    expression = to_string(arr[i+1]) + '/' + expression ; break;
                }
        }
        if(i==0 || i==1) expression += ')';
    }
    // cout<<expression<<endl;
    return expression+"=24";
}

//以字符形式输出结果等于24的表达式2
string getExpression2(array<float,4> const arr,array<int,3> const opArr)
{
    string expression= "";
    bool f=true;
    for(int i=0;i<3;++i){
        switch(opArr[i]){
            case 0: 
                if(i!=1){
                    if(f) expression += '(' + to_string(arr[i]) + '+' + to_string(arr[i+1]) + ')';
                    else expression = '(' + to_string(arr[i]) + '+' + to_string(arr[i+1]) + ')' + expression;
                }
                else{
                    expression += '+';
                }
                break;
            // expression += '+' + to_string(arr[i+1]) ; break;
            case 1: 
                if(i!=1){
                    if(f) expression += '(' + to_string(arr[i]) + '-' + to_string(arr[i+1]) + ')';
                    else expression = '(' + to_string(arr[i]) + '-' + to_string(arr[i+1]) + ')' + expression;
                }
                else{
                    expression += '-';
                }
                break;
            case 2: 
                if(i!=1){
                    if(f) expression += '(' + to_string(arr[i]) + '*' + to_string(arr[i+1]) + ')';
                    else expression = '(' + to_string(arr[i]) + '*' + to_string(arr[i+1]) + ')' + expression;
                }
                else{
                    expression += '*';
                }
                break;
            case 3: 
                if(i!=1){
                    if(f) expression += '(' + to_string(arr[i]) + '/' + to_string(arr[i+1]) + ')';
                    else expression = '(' + to_string(arr[i]) + '/' + to_string(arr[i+1]) + ')' + expression;
                }
                else{
                    expression += '/';
                }
                break;
            case 4: 
                if(i!=1){
                    if(f) expression += '(' + to_string(arr[i+1]) + '-' + to_string(arr[i]) + ')';
                    else expression = '(' + to_string(arr[i+1]) + '-' + to_string(arr[i]) + ')' + expression;
                }
                else{
                    expression = '-' + expression;
                    f = false;
                }
                break;
            case 5: 
                if(i!=1){
                    if(f) expression += '(' + to_string(arr[i+1]) + '/' + to_string(arr[i]) + ')';
                    else expression = '(' + to_string(arr[i+1]) + '/' + to_string(arr[i]) + ')' + expression;
                }
                else{
                    expression = '/' + expression;
                    f=false;
                }
                break;
        }
    }
    return expression+"=24";
}


//判断给定的四个数字是不是可以通过加减乘除运算得到24
void check(array<float,4> arr)
{
    int op_value=0;
    string expression;
    /*因为重新定义了反减和反除两种运算，现在总共有6种运算符，
    算术表达式中需要用到三个运算符，每一个位置的运算符都有6种可能，
    因此共有6^3=216种情况。
    用数字代替运算符：{{0:"+"},{0:"-"},{0:"*"},{0:"/"},{0:"~-"},{0:"~/"},}
    */
    for(op_value=0;op_value<216;++op_value){
        flag=true;
        expression="";
        array<int,3> opArr;
        //得到三个位置运算符的排列
        opArr[0]=op_value%6;
        opArr[1]=op_value/6%6;
        opArr[2]=op_value/36;
        /*定义了反减和反除运算符后，算术表达式中的运算符就都满足交换律了。
        包括使用括号的情况，原本总共7中运算顺序，使用交换律后只有两种运算顺序，
        因为其他运算顺序都可以通过交换律转换为这两种。
        1. 从左到右依次计算：((a ※ b) ※ c) ※ d
        2. 先计算前后两个数字的结果，再计算这两个结果的运算结果：(a ※ b) ※ (c ※ d)

        */
        if(compute(compute(compute(arr[0],arr[1],opArr[0]),arr[2],opArr[1]),arr[3],opArr[2])==24 && flag==true){
            expression = getExpression1(arr,opArr);
            cout<<expression<<endl;
        }
        flag=true;
        expression=""; //计算第二种表达式时记得清空表达式
        if(compute(compute(arr[0],arr[1],opArr[0]),compute(arr[2],arr[3],opArr[2]),opArr[1])==24 && flag==true){
            expression = getExpression2(arr,opArr);
            cout<<expression<<endl;
        }
    }
}

//求序列的全排列
void getPermutation(array<float,4> arr)
{
    sort(arr.begin(),arr.end());
    do{
        // display(arr);
        //判断每一个全排列是不是可以通过运算得到24
        check(arr);
    }while(next_permutation(arr.begin(),arr.end()));
}

int main(int argc,char **argv)
{
    array<float,4> arr;
    string part=" A234567891JKQ";
    bool inputErr=false;
    for(int i=0;i<4;++i){
        string temp;
        cin>>temp;
        if(temp=="10") arr[i] = stof(temp);
        else if(part.find(temp) != string::npos && part.find(temp) !=10){
            arr[i]=part.find(temp);
        }
        else{
            inputErr=true;
        }
    }
    if(inputErr){
        cout<<"ERROR"<<endl;
        return 0;
    }
    // display(arr);
    getPermutation(arr);
    return 0;
}

运行结果复制（图太长）：

3 2 4 6
((3.000000-2.000000)*4.000000)*6.000000=24
(3.000000-2.000000)*(4.000000*6.000000)=24
(4.000000/(3.000000-2.000000))*6.000000=24
(4.000000*6.000000)/(3.000000-2.000000)=24
6.000000/((3.000000-2.000000)/4.000000)=24
((3.000000-2.000000)*6.000000)*4.000000=24
(3.000000-2.000000)*(6.000000*4.000000)=24
(6.000000/(3.000000-2.000000))*4.000000=24
(6.000000*4.000000)/(3.000000-2.000000)=24
4.000000/((3.000000-2.000000)/6.000000)=24
((2.000000+4.000000)*3.000000)+6.000000=24
(2.000000+4.000000)+(3.000000*6.000000)=24
(2.000000*4.000000)*(6.000000-3.000000)=24
(2.000000*4.000000)*(6.000000-3.000000)=24
(2.000000+4.000000)+(6.000000*3.000000)=24
((4.000000-2.000000)+6.000000)*3.000000=24
((4.000000/2.000000)+6.000000)*3.000000=24
(6.000000-(2.000000-4.000000))*3.000000=24
(2.000000*6.000000)+(3.000000*4.000000)=24
((6.000000/2.000000)+3.000000)*4.000000=24
(2.000000*6.000000)+(4.000000*3.000000)=24
((6.000000-2.000000)+4.000000)*3.000000=24
((2.000000*6.000000)-4.000000)*3.000000=24
(4.000000-(2.000000-6.000000))*3.000000=24
((3.000000-2.000000)*4.000000)*6.000000=24
(3.000000-2.000000)*(4.000000*6.000000)=24
(4.000000/(3.000000-2.000000))*6.000000=24
(4.000000*6.000000)/(3.000000-2.000000)=24
6.000000/((3.000000-2.000000)/4.000000)=24
((3.000000-2.000000)*6.000000)*4.000000=24
(3.000000-2.000000)*(6.000000*4.000000)=24
(6.000000/(3.000000-2.000000))*4.000000=24
(6.000000*4.000000)/(3.000000-2.000000)=24
4.000000/((3.000000-2.000000)/6.000000)=24
(3.000000*4.000000)+(2.000000*6.000000)=24
(3.000000*4.000000)+(6.000000*2.000000)=24
((3.000000*6.000000)+2.000000)+4.000000=24
(3.000000*6.000000)+(2.000000+4.000000)=24
((6.000000-3.000000)*2.000000)*4.000000=24
(6.000000-3.000000)*(2.000000*4.000000)=24
((3.000000*6.000000)+4.000000)+2.000000=24
(3.000000*6.000000)+(4.000000+2.000000)=24
((6.000000-3.000000)*4.000000)*2.000000=24
(6.000000-3.000000)*(4.000000*2.000000)=24
((4.000000+2.000000)*3.000000)+6.000000=24
(4.000000+2.000000)+(3.000000*6.000000)=24
(4.000000*2.000000)*(6.000000-3.000000)=24
(4.000000*2.000000)*(6.000000-3.000000)=24
(4.000000+2.000000)+(6.000000*3.000000)=24
((4.000000-2.000000)+6.000000)*3.000000=24
((4.000000/2.000000)+6.000000)*3.000000=24
(6.000000-(2.000000-4.000000))*3.000000=24
(4.000000*3.000000)+(2.000000*6.000000)=24
(4.000000*3.000000)+(6.000000*2.000000)=24
((4.000000+6.000000)-2.000000)*3.000000=24
(4.000000*6.000000)*(3.000000-2.000000)=24
(4.000000*6.000000)/(3.000000-2.000000)=24
(4.000000*6.000000)*(3.000000-2.000000)=24
(4.000000*6.000000)/(3.000000-2.000000)=24
(6.000000*2.000000)+(3.000000*4.000000)=24
((6.000000/2.000000)+3.000000)*4.000000=24
((6.000000-2.000000)+4.000000)*3.000000=24
(6.000000*2.000000)+(4.000000*3.000000)=24
((6.000000*2.000000)-4.000000)*3.000000=24
(4.000000-(2.000000-6.000000))*3.000000=24
((6.000000*3.000000)+2.000000)+4.000000=24
(6.000000*3.000000)+(2.000000+4.000000)=24
((6.000000-3.000000)*2.000000)*4.000000=24
(6.000000-3.000000)*(2.000000*4.000000)=24
((6.000000*3.000000)+4.000000)+2.000000=24
(6.000000*3.000000)+(4.000000+2.000000)=24
((6.000000-3.000000)*4.000000)*2.000000=24
(6.000000-3.000000)*(4.000000*2.000000)=24
((6.000000+4.000000)-2.000000)*3.000000=24
(6.000000*4.000000)*(3.000000-2.000000)=24
(6.000000*4.000000)/(3.000000-2.000000)=24
(6.000000*4.000000)*(3.000000-2.000000)=24
(6.000000*4.000000)/(3.000000-2.000000)=24

结果会有重复，但是总的运算量也不大，无所谓。

24点运算

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构&算法&人工智能