最开始我想的是全排列+枚举符号和括号的方法,但是我自己倒腾了很久还是打不对,只好向他人请教。
正解很机智——直接随意将几个数“捆绑”在一起,值存在其中一个数上,其他数标记不可再选,直到只剩下一个数,再判断这个数是否为24。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<algorithm>
5 #include<iostream>
6 using namespace std;
7
8 const double eps=0.00000001;
9 double a[4];
10 int v[4];
11
12 double mabs(double x)
13 { return x>0?x:-x; }
14
15 int dfs(int x)
16 {
17 if (x==3)
18 {
19 for (int i=0;i<4;i++)
20 if (!v[i] && mabs(a[i]-24.0)<eps) return 1;
21 return 0;
22 }
23 /*for (int i=0;i<4;i++)
24 if (!v[i])
25 for (int j=0;j<4;j++)
26 if (!v[j]&&i!=j)
27 {
28 v[j]=1;
29 double tmp=a[i],tmpp=a[j];
30
31 a[i]=tmp+tmpp;
32 if (dfs(x+1)) return 1;
33 a[i]=tmp-tmpp;
34 if (dfs(x+1)) return 1;
35 a[i]=tmpp*tmp;
36 if (dfs(x+1)) return 1;
37 a[i]=tmpp/tmp;
38 if (dfs(x+1)) return 1;
39
40 a[i]=tmp;
41 v[j]=0;
42 }*///244ms
43 for (int i=0;i<4;i++)
44 if (!v[i])
45 for (int j=i+1;j<4;j++)//区别
46 if (!v[j])
47 {
48 v[j]=1;
49 double tmp=a[i],tmpp=a[j];
50
51 a[i]=tmp+tmpp;
52 if (dfs(x+1)) return 1;
53 a[i]=tmp-tmpp;
54 if (dfs(x+1)) return 1;
55 a[i]=tmpp-tmp;//
56 if (dfs(x+1)) return 1;
57 a[i]=tmpp*tmp;
58 if (dfs(x+1)) return 1;
59 a[i]=tmpp/tmp;
60 if (dfs(x+1)) return 1;
61 a[i]=tmp/tmpp;//
62 if (dfs(x+1)) return 1;
63
64 a[i]=tmp;
65 v[j]=0;
66 }//102ms
67 return 0;
68 }
69
70 int main()
71 {
72 while (1)
73 {
74 for (int i=0;i<4;i++) scanf("%lf",&a[i]);
75 if (!a[0]) break;
76 memset(v,0,sizeof(v));
77 if (dfs(0)) printf("YES\n");
78 else printf("NO\n");
79 }
80 return 0;
81 }