程序设计II上机实验9A：算24

算24

Time limit: 1000 ms

Memory limit: 256 MB

Standard I/O

Content

给出4个小于10的正整数，你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是，是否存在一种方式使得得到的表达式的结果等于24。

这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致（这里的除法定义是实数除法）。

比如，对于5，5，5，1，我们知道5 * (5 – 1 / 5) = 24，因此可以得到24。又比如，对于1，1，4，2，我们怎么都不能得到24。

Input Description

输入数据包括多行，每行给出一组测试数据，包括4个小于10的正整数（用空格分开）。最后一组测试数据中包括4个0，表示输入的结束，这组数据不用处理。

Output Description

对于每一组测试数据，输出一行，如果可以得到24，输出“YES”；否则，输出“NO”。

Sample

INPUT

5 5 5 1
1 1 4 2
0 0 0 0

OUTPUT

YES
NO

Code

#include <stdio.h>
#include <math.h>
#define P 10e-4
#define INF 99999
int IsEqual(double a,double b)
{
    if(fabs(a-b)<=P) return 1;
    else return 0;
}
double Cal(double a,char op,double b)
{
    switch(op)
    {
        case '+': return a+b;
        case '-': return a-b;
        case '*': return a*b;
        case '/': if(b==0) return INF; else return a/b;
    }
}
int Game24(double n[])
{
    char op[]={'+','-','*','/'};
    double res[5];
    int i1,i2,i3,i4,j1,j2,j3,k,count=0;
    for(i1=0;i1<4;i1++)
    {
        for(i2=0;i2<4;i2++)
        {
            if(i2!=i1)
            {
                for(i3=0;i3<4;i3++)
                {
                    if(i3!=i2 && i3!=i1)
                    {
                        for(i4=0;i4<4;i4++)
                        {
                            if(i4!=i3 && i4!=i2 && i4!=i1)
                            {
                                for(j1=0;j1<4;j1++)
                                {
                                    for(j2=0;j2<4;j2++)
                                    {
                                        for(j3=0;j3<4;j3++)
                                        {
                                            res[0]=Cal(Cal(Cal(n[i1],op[j1],n[i2]),op[j2],n[i3]),op[j3],n[i4]);
                                            res[1]=Cal(Cal(n[i1],op[j1],n[i2]),op[j2],Cal(n[i3],op[j3],n[i4]));
                                            res[2]=Cal(Cal(n[i1],op[j1],Cal(n[i2],op[j2],n[i3])),op[j3],n[i4]);
                                            res[3]=Cal(n[i1],op[j1],Cal(Cal(n[i2],op[j2],n[i3]),op[j3],n[i4]));
                                            res[4]=Cal(n[i1],op[j1],Cal(n[i2],op[j2],Cal(n[i3],op[j3],n[i4])));
                                            for(k=0;k<5;k++)
                                            {
                                                if(IsEqual(24,res[k]))
                                                {
                                                    return 1;    
                                                }
                                            }
                                        }    
                                    }    
                                }
                            }
                        }                
                    }            
                }                
            }
        }
    }
    return 0;
}
int main()
{
    double n[4];
    while(1)
    {
        scanf("%lf%lf%lf%lf",&n[0],&n[1],&n[2],&n[3]);
        if(!n[0] && !n[1] && !n[2] && !n[3]) break;
        if(Game24(n)) printf("YES\n"); else printf("NO\n");
    }
    return 0;
}