算24

题目链接：http://noi.openjudge.cn/ch0205/1789/
总时间限制: 3000ms 内存限制: 65536kB

描述

给出4个小于10的正整数，你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是，是否存在一种方式使得得到的表达式的结果等于24。
这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致（这里的除法定义是实数除法）。
比如，对于5，5，5，1，我们知道5 * (5 – 1 / 5) = 24，因此可以得到24。又比如，对于1，1，4，2，我们怎么都不能得到24。

输入

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

输出

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

样例输入

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

样例输出

YES
NO

算法分析：

参考北大郭炜老师在中国大学mooc的算法基础课程。

n个数算24，必有两个数要先算。这两个数算的结果，和剩余n-2个数，就构成了n-1个数求24的问题。

所以可以递归枚举先算的两个数，以及这两个数的运算方式。

递归的边界条件：一个数算24 。

注意：浮点数比较是否相等，不能用 ==

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 double a[5];
 6 #define EPS 1e-6
 7 
 8 bool isZero(double x)
 9 {  return fabs(x) <= EPS;  }
10 bool count24(double a[],int n)
11 {//用数组a里的 n个数，计算24
12     if( n == 1 ) 
13     {
14         if(isZero( a[0] - 24) ) return true;
15         else return false;
16     }
17     double b[5];
18     for(int i = 0;i < n-1; ++i)
19         for(int j = i+1;j < n; ++j)//枚举两个数的组合
20         { 
21             int m = 0; //还剩下m个数, m = n - 2
22             for(int k = 0; k < n; ++k)
23                 if( k != i && k!= j) b[m++] = a[k];//把其余数放入b
24             b[m] = a[i]+a[j];
25             if(count24(b,m+1)) return true;
26             
27             b[m] = a[i]-a[j];
28             if(count24(b,m+1)) return true;
29             
30             b[m] = a[j]-a[i];
31             if(count24(b,m+1)) return true;
32             
33             b[m] = a[i]*a[j];
34             if(count24(b,m+1)) return true;
35             
36             if( !isZero(a[j]))
37             {
38                 b[m] = a[i]/a[j];
39                 if(count24(b,m+1))
40                 return true;
41             }
42             if( !isZero(a[i])) 
43             {
44                 b[m] = a[j]/a[i];
45                 if(count24(b,m+1))
46                 return true;
47             }
48         }
49     return false;
50 }
51 int main()
52 {
53     while(true) 
54     {
55         for(int i = 0;i < 4; ++i) cin >> a[i];
56         if( isZero(a[0])) break;
57         if( count24(a,4)) cout << "YES" << endl;
58         else cout << "NO" << endl;
59     }
60     return 0;
61 }

注意：上述代码似乎没有考虑到运算数的原始顺序的问题，但其实从题目举的例子来看，数的顺序可以改变。