题解 | #24点游戏算法#

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

double compute(double x,double y,char op){
    switch (op) {
        case '+': return x+y;
        case '-': return x-y;
        case '*': return x*y;
        case '/': return y!=0?x/y:0;
        default: return 0;
    }
}

bool dfs(vector<double> &num,int n,vector<char> &op){
    if (num[3]>24 || (n==3&&num[3]!=24)){
        // 大于24点、三个符号位填充完毕结果不等于24
        return false;
    } else if (n==3&&num[3]==24){
        return true;
    }
    for (auto o:op) {
        double tem = num[n+1];
        num[n+1] = compute(num[n],num[n+1],o);
        if (!dfs(num,n+1,op)){
            num[n+1] = tem;
        } else{
            return true;
        }
    }
    return false;
}

int main(){
    vector<double> arr(4,0);
    vector<char> op = {'+','-','*','/'};
    while (cin>>arr[0]>>arr[1]>>arr[2]>>arr[3]){
        bool flag = false;
        sort(arr.begin(),arr.end());
        do {
            if (flag) break;
            flag = dfs(arr,0,op);
        } while (next_permutation(arr.begin(),arr.end()));
        if (flag) cout<<"true"<<endl;
        else cout<<"false"<<endl;
    }

    return 0;
}