题解 | 24点游戏算法

带括号的算法：

#include <climits>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

constexpr double EPS = 1e-6;

double count2(double a, char op, double b)
{
    switch (op)
    {
    case '+': return a+b;
    case '-': return a-b;
    case '*': return a*b;
    default: 
        if (b != 0) return a/b; // default is /
        else return INT_MAX;
    }
}

double count3(double a, char op1, double b, char op2, double c)
{
    if (op1 == '+' || op1 == '-')
        return count2(a, op1, count2(b,op2,c));
    else 
        return count2(count2(a,op1,b), op2, c);
}

double count4(double a, char op1, double b, char op2, double c, char op3, double d)
{
    if (op2 == '+' || op2 == '-')
        return count2(count2(a, op1, b), op2, count2(c, op3, d));
    else if (op1 == '+' || op1 == '-')
        return count2(a, op1, count3(b, op2, c, op3, d));
    else if (op3 == '+' || op3 == '-')
        return count2(count3(a, op1, b, op2, c), op3, d);
    else return count2(count2(a,op1,b),op2, count2(c, op3, d)); // 可以把else合并到任意上面一个
}

vector<vector<char>> operSeq{};
void getOperSeq(vector<char>& operators, vector<char>& operTrack)
{
    if (operTrack.size()==3)
    {
        operSeq.push_back(operTrack);
        return;
    }

    for (int j{}; j<4; ++j)
    {
        operTrack.push_back(operators[j]);
        getOperSeq(operators, operTrack);
        operTrack.pop_back();
    }
}

vector<vector<int>> numSeq{};
void getNumSeq(vector<int>& nums, vector<int>& numTrack, vector<int>& used)
{
    if (numTrack.size() == 4)
    {
        numSeq.push_back(numTrack);
        return;
    }
    for (int i{}; i<4; ++i)
    {
        if (used[i] == 1) continue;
        used[i] = 1;
        numTrack.push_back(nums[i]);
        getNumSeq(nums, numTrack, used);
        numTrack.pop_back();
        used[i] = 0;
    }
}

bool calc(vector<int>& nums, vector<char>& oper)
{
    vector<double> res{};
    res.push_back(count4(nums[0], oper[0], nums[1], oper[1], nums[2], oper[2], nums[3]));

    res.push_back(count2(
                        count3(nums[0], oper[0], nums[1], oper[1], nums[2]), 
                        oper[2], nums[3]
                ));
    res.push_back(count2(
                        nums[0], oper[0],
                        count3(nums[1], oper[1], nums[2], oper[2], nums[3])
                ));
    res.push_back(count2(
                        count2(nums[0],oper[0],nums[1]), oper[1], count2(nums[2], oper[2], nums[3])
                ));
    res.push_back(count2(
                        count2(count2(nums[0],oper[0],nums[1]), oper[1], nums[2]), oper[2], nums[3]
                ));
    res.push_back(count2(
                        nums[0],oper[0],count2(count2(nums[1], oper[1], nums[2]), oper[2], nums[3])
                ));
    res.push_back(count2(
                        nums[0],oper[0],count2(nums[1], oper[1], count2(nums[2], oper[2], nums[3]))
                ));

    for (const auto& d: res)
    {
        if (d-24 < EPS && d-24 > -EPS) return true;
    }
    return false;
}

bool dfs(vector<vector<int>>& numSeq, vector<vector<char>>& operSeq)
{
    for (int i{}; i<24; i++)
    {
        for (int j{}; j<64; ++j)
        {
            if (calc(numSeq[i], operSeq[j])) return true;
        }
    }

    return false;
}

int main() {
    int n{};
    vector<int>nums{};
    for (int i{}; i<4; ++i)
    {
        cin>>n;
        nums.emplace_back(n);
    }
    vector<char> operators{'+','-','*','/'};
    // get oper sequences
    vector<char> operTrack{};
    vector<int> numTrack{};
    vector<int> used(4);
    getOperSeq(operators, operTrack);
    getNumSeq(nums, numTrack, used);
    if (dfs(numSeq, operSeq))
        std::cout << "true";
    else std::cout << "false";

    return 0;
}
// 64 位输出请用 printf("%lld")