华为机试题67-24点游戏算法

描述

给出4个1-10的数字，通过加减乘除运算，得到数字为24就算胜利,除法指实数除法运算,运算符仅允许出现在两个数字之间,本题对数字选取顺序无要求，但每个数字仅允许使用一次，且需考虑括号运算

此题允许数字重复，如3 3 4 4为合法输入，此输入一共有两个3，但是每个数字只允许使用一次，则运算过程中两个3都被选取并进行对应的计算操作。

输入描述：

读入4个[1,10]的整数，数字允许重复，测试用例保证无异常数字。

输出描述：

对于每组案例，输出一行表示能否得到24点，能输出true，不能输出false

示例1

输入：

7 2 1 10

输出：

true

这题应该算是难题吧，LeetCode里就是难题，华为机试里竟然是中等题。

我的方法很笨，用的是递归。

解题思路：

题目描述输入4个数，判断是否能通过四则运算（需考虑括号情况）得到24。

这里的考虑括号情况其实是唬人了，括号的作用也就是加强运算的优先级，我们只要将4个数四则运算的所有的情况加以考虑就可以。

比如4个数为：4，1，8，7

通过四则运算（8-4）*（7-1）能得到24，这里的括号可有可无，这个结果无非是：

首先选择8和4，进行减法运算，得到4，然后这个4与原先未参与运算的1和7组成：4，1，7

然后选择7和1，进行减法运算，得到6，然后这个6与原先未参与运算的4组成：4，6

最后选择4和6，进行乘法运算，就得到24

这也就是上面所说的不用被括号迷糊的原因了。

实际上，4个数，我们首先选择其中2个数，进行加减乘除任一运算，此时的运算结果再与原来未参加运算的2个数组成新的3个数，在3个数的基础上，判断通过四则运算是否能够得到24。通过以上分析，我们会想到利用递归来解题。递归都需要设置边界条件，这里的边界条件很简单，就是只剩1个数参与四则运算的时候，这个数就是4个数通过四则运算得到的最终结果，只需要判断其是否等于24即可；还有一些细节需要注意，比如说：

1、除数不能为0，进行除法运算的时候需要提前判断

2、实数除法运算是有较小误差的，结果不一定就等于24，只要结果与24误差足够小就能认为运算结果就是24，可以利用库函数fabs来求解两实数间的误差绝对值

3、如果某次运算结果不等于24，注意恢复运算前的数据，比如只剩2个数：4和6时，先试探加法得到10，将结果改为10和10001（此数说明为无效数），发现10不等于24，这次递归结束后，需要恢复成原来的4和6，同理进行减法运算得不到24，再恢复，进行乘法发现得到24，就可以结束了。

代码如下：

#include <stdio.h>
#include <math.h>
#define    MAX    10001        //用以表示无效数，因为4个数都不大于10，累乘也不过10000
int dfs(double num[])
{
    int i,j,cnt=0;
    double a,b;
    for(i=0;i<4;i++)
    {
        if(num[i]!=MAX)
            cnt++;            //cnt用来记录此次运算有几个数
    }
    if(cnt==1)                //只有一个数时，判断是否为24
    {
        for(i=0;i<4;i++)
        {
            if(num[i]!=MAX)
                if(fabs(num[i]-24)<=1e-6)
                    return 1;        //是24，返回1
                else
                    return 0;        //不是24，返回0
        }
    }
    else
    {
        for(i=0;i<4;i++)                
        {
            if(num[i]!=MAX)            //有效数才能参与运算
            {
                for(j=0;j<4;j++)
                {
                    if(i==j||num[j]==MAX)    //每个数只能被计算1次
                        continue;
                    a=num[i];
                    b=num[j];
                    
                    num[i]=a+b;        //加法运算，存储运算结果
                    num[j]=MAX;        //另一个数改为无效数
                    if(dfs(num))
                        return 1;
                    num[i]=a;      //若没有return，表示加法结果得不到24，恢复加法运算前的数字
                    num[j]=b;
                
                    num[i]=a-b;        //继续试探减法运算，下同
                    num[j]=MAX;
                    if(dfs(num))
                        return 1;
                    num[i]=a;
                    num[j]=b;
                
                    if(b!=0)
                    {
                        num[i]=a/b;
                        num[j]=MAX;
                        if(dfs(num))
                            return 1;
                        num[i]=a;
                        num[j]=b;
                    }
                
                    num[i]=a*b;
                    num[j]=MAX;
                    if(dfs(num))
                        return 1;
                    num[i]=a;
                    num[j]=b;
                }  
            }

        }
    }
    return 0;         //对于这次的有效数字，每轮四则运算都得不到24，返回0
}
int main()
{
    int i,temp;
    double num[4];
    for(i=0;i<4;i++)
    {
        scanf("%d",&temp);   //题目要求输入4个整数，这里转换成浮点数，不然后续的除法运算会出错
        num[i]=temp*1.0;
    }
    if(dfs(num))
        printf("true\n");
    else
        printf("false\n");
    return 0;
}