题解 | 24点游戏算法

#include<iostream>
#include<algorithm>
using namespace std;

char ops[4] = {'+', '-', '*', '/'};
//两数计算
double cal(double db1, double db2, char op) {
    double result;
    switch (op) {
        case '+':
            result = db1 + db2;
            break;
        case '-':
            result = db1 - db2;
            break;
        case '*':
            result = db1 * db2;
            break;
        case '/':
            result = db1 / db2;
            break;
    };
    return result;
};
int main() {
    double num[4];
    cin >> num[0] >> num[1] >> num[2] >> num[3];
    sort(num, num + 4); //初始化为最小排序
    do                  //生成所有排列
    {//顺序计算，不加括号
        for (int i = 0; i < 4; i++) {
            double res;
            if (i == 3 && num[1] == 0)continue;
            else res = cal(num[0], num[1], ops[i]);
            for (int j = 0; j < 4; j++) {
                if (j == 3 && num[2] == 0)continue;
                else res = cal(res, num[2], ops[j]);
                for (int k = 0; k < 4; k++) {
                    if (k == 3 && num[3] == 0)continue;
                    else res = cal(res, num[3], ops[k]);
                    if (res == 24) {
                        cout << "true";
                        return 0;
                    }
                }
            }
        }
        //加括号，先计算num[1]和num[2]
        for (int i = 0; i < 4; i++) {
            double val12;
            double res;
            if (i == 3 && num[2] == 0)continue;
            else val12 = cal(num[1], num[2], ops[i]);
            //再计算val12和num[3]
            for (int j = 0; j < 4; j++) {
                if (j == 3 && num[3] == 0)continue;
                else res = cal(val12, num[3], ops[j]);
                for (int k = 0; k < 4; k++) {
                    if (k == 3 && res == 0)continue;
                    else res = cal(num[0], res, ops[k]);
                    if (res == 24) {
                        cout << "true";
                        return 0;
                    }
                }
            }
            //再顺序计算
            for (int j = 0; j < 4; j++) {
                if (j == 3 && val12 == 0)continue;
                else res = cal(num[0], val12,  ops[j]);
                for (int k = 0; k < 4; k++) {
                    if (k == 3 && num[3] == 0)continue;
                    else res = cal(res, num[3], ops[k]);
                    if (res == 24) {
                        cout << "true";
                        return 0;
                    }
                }
            }

        }
        //加括号，先计算num[2]和num[3]
        for (int i = 0; i < 4; i++) {
            double val23;
            double res;
            if (i == 3 && num[3] == 0)continue;
            else val23 = cal(num[2], num[3], ops[i]);
            //再计算val23和num[1]
            for (int j = 0; j < 4; j++) {
                if (j == 3 && num[1] == 0)continue;
                else res = cal(val23, num[1], ops[j]);
                for (int k = 0; k < 4; k++) {
                    if (k == 3 && num[0] == 0)continue;
                    else res = cal(res, num[0], ops[k]);
                    if (res == 24) {
                        cout << "true";
                        return 0;
                    }
                }
            }
            //再顺序计算
            for (int j = 0; j < 4; j++) {
                if (j == 3 && num[1] == 0)continue;
                else res = cal(num[0], num[1], ops[j]);
                for (int k = 0; k < 4; k++) {
                    if (k == 3 && val23 == 0)continue;
                    else res = cal(res, val23, ops[k]);
                    if (res == 24) {
                        cout << "true";
                        return 0;
                    }
                }
            }

        }

    } while (next_permutation(num,num + 4)); //next_permutation() 按字典序生成下一个排列，直到最大排列（如 [4,3,2,1]）后返回 false。
    cout << "false";
    return 0;
}