题目描述

在leetcode 上找的一个题，

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24

例如：[4,1,8,7]

(8-4)*(7-1) = 24

输出是否能够得到24 返回bool值即可，不必给出算式。

算法分析

在这里插入图片描述

算法的描述基本就是如此，接下来就是回溯的过程

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define SIZE 4class Myclass{
   public:		//初始化运算符，括号只是改变运算的顺序，在回溯算法中包含了所有的运算顺序	//所以不用加入括号运算符    Myclass()    {
           _sign.push_back('+');        _sign.push_back('-');        _sign.push_back('*');        _sign.push_back('/');    }/*************************************************************************************** * 回溯算法： *      选取数组中的任意两个值进行运算，将运算后的结果加入到数组中，并将选取的两个值删除 *      递归进入下一个状态，此时数组中由三个值，每进行一次递归，数组中减少一个元素，直到 *      数组中的元素个数为1时，判断该值是否为24若是，则返回true 否则返回false. * *      本次递归出来后恢复递归前的状态，进行下一个运算符的计算， * *      括号只是改变运算的顺序，由于回溯算法包含了所有的情况，所以不需要考虑括号的情况 * **************************************************************************************/    bool fun(vector
      
        _nums)    {
       	//递归的出口，当数组中只有一个元素的时候        if(_nums.size() == 1)         {
               if(_nums[0] == 24)                return true;            else                return false;        }        //双重循环用来选取两个不同的的元素进行操作        for(int i = 0; i < _nums.size(); i++)        {
               for(int j = i+1; j < _nums.size(); j++)            {
               	//遍历符号数组，选择相应的符号                for(int k = 0; k < _sign.size(); k++)                {
                       double data = 0;                    //如果是 “+” 或者 “*” 不区分左右操作数                    //“-” 和 “/” 区分左右操作数                    //如果是 “+” 或者是 “*”求出两个元素运算后的结果                    if(_sign[k] == '+' || _sign[k] == '*')                    {
                           switch(_sign[k])                        {
                               case '+':                                data = _nums[i] + _nums[j];                                break;                            case '*':                                data = _nums[i] * _nums[j];                                break;                            default:                                break;                        }                        double tmpi = _nums[i];                        double tmpj = _nums[j];                        //删除两个元素                        _nums.erase(_nums.begin()+i);                        _nums.erase(_nums.begin()+j-1);                        //将运算结果加入数组中                        _nums.push_back(data);                        //如果返回true 则说明可以构成，直接返回                        if(fun(_nums))                        {
                               return true;                        }                        //如果返回false,恢复数组的状态，将data删除                        //然后将删除的两个元素加入到数组中进行下一个运算符的选择                        _nums.pop_back();                        _nums.insert(_nums.begin()+i,tmpi);                        _nums.insert(_nums.begin()+j,tmpj);                    }                    //如果选择 “-” 或 “/”                    else                    {
                           double tmpi = _nums[i];                        double tmpj = _nums[j];                        double data1;                        double data2;                        switch(_sign[k])                        {
                               case '-':                                {
                                       data1 = _nums[i] - _nums[j];                                    data2 = _nums[j] - _nums[i];                                     break;                                }                            case '/':                                {
                                       data1 = tmpi / tmpj;                                    data2 = tmpj / tmpi;                                    break;                                }                        }                        //删除两个选出的元素                        _nums.erase(_nums.begin()+i);                        _nums.erase(_nums.begin()+j-1);                        _nums.push_back(data1);                        //如果可以满足则直接返回                        if(fun(_nums))                        {
                               return true;                        }                        _nums.pop_back();                        //否则交换左右操作数后再进行迭代                        _nums.push_back(data2);                        if(fun(_nums))                        {
                               return true;                        }                        //不满足的话回到初始的状态。                        _nums.pop_back();                        _nums.insert(_nums.begin()+i,tmpi);                        _nums.insert(_nums.begin()+j,tmpj);                    }                }            }        }        return false;    }private:    vector
       
         _sign;};//设置原数组void setNums(vector
        
          &_nums){ for(int i = 0; i < SIZE; i++) { double data; cin >> data; _nums.push_back(data); }}int main(){ Myclass my; vector
         
           _nums; setNums(_nums); cout << my.fun(_nums) << endl; return 0;}