题解 | 24点游戏算法

//DFS+回溯算法，每次只能直接处理2个数，因此先将4个数变为3个数，再将三个数变为两个数就可以处理了
#include<iostream>
using namespace std;
#include<vector>
#include<cmath>
//使用double和除法运算时可能会损失精度，定义一个极小值来避免误差
const double epsilon = 1e-6;

bool dfs(vector<double>nums)
{
    int size=nums.size();
    //先写递归出口，nums数组每次处理两个数后size-1，当只剩最后一个数时即可判断
    if(size==1)
    {
        return fabs(nums[0]-24) < epsilon;
    }

    //每次选择两个数进行运算处理，将结果放回原容器后进行下一步处理
    for(int i=0; i< size; i++)
    {
        for(int j=i+1; j<size; j++)
        //当size为4时，共有取第1 2，1 3，1 4，2 3，2 4，3 4个数 共六种情况
        {
            //将不参与运算的剩余数字存放next容器中用于下一步的递归
            vector<double> next;
            for(int k=0; k<size ;k++)
            {
                if(k!=i && k!=j)
                next.push_back(nums[k]);
            }

            //用一个容器存放两个数的运算结果
            double a= nums[i],b=nums[j];
            vector<double>res={ a+b, a-b, b-a, a*b };
            //计算除法时需要注意除数不能为0
            if(a!=0)
            res.push_back(b/a);
            if(b!=0)
            res.push_back(a/b);

            //依次处理nums[i]和nums[j]的所有运算结果
            for(auto it : res)
            {
                //把得到的结果放回next容器，这样数字数量就-1，然后进行下一次递归
                next.push_back(it);
                if(dfs(next))
                return true;
                //如果没有return true说明这个next数组不能满足要求，要尝试下一个next
                next.pop_back();
            }
        }
    }
    //尝试完了所有组合都没有成功
    return false;
}


int main()
{
    vector<double> nums;//除法可能出现小数
    int num;
    while(cin>>num)
    {
        nums.push_back(num);
    }
    
    if(dfs(nums))
    {
        cout<<"true";
    }
    else 
    {
        cout<<"false";
    }
    return 0;
}