题解 | 24点游戏算法

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
//误差容忍度
const double EPSILON = 1e-6;

bool dfs(vector<double> &nums){
    if(nums.size() == 1){
        return fabs(nums[0] - 24) < EPSILON;
    }

    for(int i=0;i<nums.size();i++){
        for(int j=i+1;j<nums.size();j++){
            double a = nums[i], b = nums[j];
            vector<double> next;
            for(int n=0;n<nums.size();n++){
                if(n != i && n != j){
                    next.push_back(nums[n]);
                }
            }
            //枚举所有运算
            //a+b
            next.push_back(a+b);
            if(dfs(next)){
                return true;
            }
            next.pop_back();
            //a-b
            next.push_back(a-b);
            if(dfs(next)){
                return true;
            }
            next.pop_back();
            //b-a
            next.push_back(b-a);
            if(dfs(next)){
                return true;
            }
            next.pop_back();
            //a*b
            next.push_back(a*b);
            if(dfs(next)){
                return true;
            }
            next.pop_back();
            //a/b
            if(fabs(b) > EPSILON){
                next.push_back(a/b);
                if(dfs(next)){
                    return true;
                }
                next.pop_back();
            }
            //b/a
            if(fabs(a) > EPSILON){
                next.push_back(b/a);
                if(dfs(next)){
                    return true;
                }
                next.pop_back();
            }

        }
    }
    return false;
}

int main() {
    int a,b,c,d;
    vector<double> nums;
    while(cin >> a >> b >> c >> d){
    vector<double> nums = {(double)a,(double)b,(double)c,(double)d};
    if(dfs(nums)){
        cout << "true";
    }else{
        cout << "false";
    }   
    }
    
}
// 64 位输出请用 printf("%lld")