華為機試HJ67：24點游戲演算法

作者：Steven
著作權宣告：著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處

題目描述：

問題描述：給出4個1-10的數字，通過加減乘除，得到數字為24就算勝利
輸入：
4個1-10的數字，[數字允許重復，但每個數字僅允許使用一次，測驗用例保證無例外數字，
輸出：

true or false

本題含有多組樣例輸入，

輸入描述：

輸入4個int整數

輸出描述：

回傳能否得到24點，能輸出true，不能輸出false

示例：

輸入：

7 2 1 10

輸出：

true

解題思路：

本題是深度優先遍歷dfs的經典題目：輸入4個1-10的數字，用加減乘除使其結果為24，用dfs函式進行遞回遍歷求解，當計算到第四步時，step為3，此時判斷是否為24，若有結果則令flag為true；宣告num陣列存放數字，宣告visit陣列存放當前數字是否可用，

假設輸入數字為7654，則第一個遍歷為7+6+5+4，再7+6+5-4，，，再7+6-5+4，，，，再7+6+4+5，，，以此類推，另外，dfs扔進去的和是前面的所有值計算完的結果再操作后面的值，換句話說，7+6+5*4，它扔進去的是（7+6+5）*4，雖然此時計算的結果和預想的不一樣，別忘了還有排序，后面會有5*4+7+6的計算運算式，這樣就確保了該計算的運算式依然會進行計算，

注意:因為sum初始為0,所以要考慮一下不同情況,不然會出現0*X=0，

測驗代碼：

#include <iostream>

using namespace std;

double num[4];
bool flag=false;
bool visit[4]={0};

void dfs(int step,double sum)
{
    if(flag)
        return;
    if(step==3)
    {
        if(sum==24.)
        {
            flag=true;
            return;
        }
    }
    else{
        step++;
        for(int i=0;i<4;++i)
        {
            if(!visit[i])
            {
                visit[i]=true;
                dfs(step,sum+num[i]);
                dfs(step,sum-num[i]);
                if(step!=0){
                    dfs(step,sum*num[i]);
                    dfs(step,sum/num[i]);
                }
                visit[i]=false;
                if(flag)
                    return;
            }
        }
    }
    
}

int main()
{
    while(cin>>num[0]>>num[1]>>num[2]>>num[3])
    {
        dfs(-1,0);
        if(flag)
        {
            cout<<"true"<<endl;
        }
        else{
            cout<<"false"<<endl;
        }

        flag=false;
        num[4]={0};
        visit[4]={0};
    }
    return 0;
}

后來測驗我發現，1 9 1 2這個例子過不了，但是(9-1)*(2+1)=24，這是因為上面的演算法考慮括號操作不周全導致的，牛客一名大佬“ultraji” 所提供的的演算法思路更完善些，在此分享給大家，

其邏輯是：借用next_permutation函式排布4個數字的順序，往里面塞入3個運算子，再用for回圈處理各種可能的括號情況，其代碼如下：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

double op(double a, double b, int opera)
{
    if(opera == 0) return a+b;
    else if(opera == 1) return a-b;
    else if(opera == 2) return a*b;
    else if(opera == 3) return a/b;
    return 0;
}

bool cal24(vector<double> a, vector<int> o)
{
    // 考慮括號導致優先級變化
    bool flag = false;
    if(o.empty()) {
        if( fabs(a[0]-24.0) < 0.01) flag = true;
    } else {
        for (int i = 0; i < o.size() && !flag; i++)
        {
            a[i] = op(a[i], a[i+1], o[i]);
            a.erase(a.begin()+i+1);
            o.erase(o.begin()+i);
            flag |= cal24(a, o);
        }
    }
    return flag;
}

int main()
{
    double a[4];
    int o[3];
    while(cin >> a[0] >> a[1] >> a[2] >> a[3])
    {
        bool flag = false;
        sort(a, a+4);
        do {
            for(int i = 0; i < 4 && !flag; i++) {
                o[0] = i;
                for(int j = 0; j < 4 && !flag; j++) {
                    o[1] = j; 
                    for(int k = 0; k < 4 && !flag; k++) {
                        o[2] = k;
                        vector<double> va(a, a+4);
                        vector<int> vo(o, o+3);
                        if(cal24(va, vo)) flag = true;
                    }
                }
            }
        } while (next_permutation(a, a+4) && !flag);
        if( flag ) cout << "true" << endl;
        else cout << "false" << endl;
    }
    return 0;
}