7-3 大家一起来玩游戏（20 分)

以你之姓@ 2022-04-23 14:14 185阅读 0赞

### 题目描述： ###

24点是一种益智游戏，24点是把4个整数（一般是正整数）通过加减乘除以及括号运算，使最后的计算结果是24的一个数学游戏，24点可以考验人的智力和数学敏感性，它能在游戏中提高人们的心算能力。 24点通常是使用扑克牌来进行游戏的，一副牌中抽去大小王后还剩下52张（如果初练也可只用1～10这40张牌），任意抽取4张牌（称为牌组），用加、减、乘、除（可加括号）把牌面上的数算成24。每张牌必须只能用一次，如抽出的牌是3、8、8、9，那么算式为（9－8）×8×3或3×8÷（9－8）或（9－8÷8）×3等。比如 1 5 5 5，算式为 5\*(5-(1/5));

输入格式:  
第一行输入n，表示n组测试数据，后面n行，每一行输入4个1-10的数字。\[数字允许重复，测试用例保证无异常数字\]

输出格式:  
每组测试数据如果可以满足24点，则输出True,否则输出False，空格间隔后输出下一组结果，所有输出只占一行（行末无多余空格）。

输入样例:  
2  
1 5 5 5  
5 1 1 1  
输出样例:  
True False

###### 分析： ######

本题第一反应就是用dfs，把六种情况都要考虑到。  
注意减和除有两种情况。 然后初始状态要从0开始。一开始直接从那个数字开始了，没考虑清楚。导致一组数据都过不了。  
当然，这个题还有一个坑：  
3*5+2*6  
像这种情况，如果单纯的用六种情况的dfs是表示不出来的。  
所以，需要把dfs在改进一下。  
改进的方法： 有点绕。  
在dfs里面用两层循环。  
将每种情况的值保存在 a\[j\]里面。这样就可以将上面那种情况考虑到了。  
具体见代码：

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    int mark=0;
    double a[4];
    int vis[4];
    void dfs(int step)
    {
        
        if(step==3)//已经对四个数进行了操作
        {
            int i;
            for(i=0; i<4; i++)
                if(vis[i]==0)
                    break;
            if(a[i]==24)
                mark=1;
            return ;
        }
        for(int i=0; i<4; i++)
            for(int j=i+1; j<4; j++)
            {
                if(vis[i]==0&&vis[j]==0)
                {
                    double x=a[i],y=a[j];//必须double型的数据
                    vis[i]=1;//标记一下
                    a[j]=x+y;
                    dfs(step+1);
                    a[j]=x-y;
                    dfs(step+1);
                    a[j]=y-x;
                    dfs(step+1);
                    a[j]=x*y;
                    dfs(step+1);
                    a[j]=x/y;
                    dfs(step+1);
                    a[j]=y/x;
                    dfs(step+1);
                    vis[i]=0;//需要回溯 
                    a[j]=y;
                }
            }
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        int cnt=1;
        while(T--)
        {
            scanf("%lf%lf%lf%lf",&a[0],&a[1],&a[2],&a[3]);
            mark=0;
            memset(vis,0,sizeof(vis));
            dfs(0);
            if(mark==1)
            {
                if(cnt==1)
                    printf("True");
                else
                    printf(" True");
            }
            else if(cnt==1)
                printf("False");
            else
                printf(" False");
            cnt++;
        }
    }