首页 > 代码库 > HNU 12886 Cracking the Safe(暴力枚举)
HNU 12886 Cracking the Safe(暴力枚举)
题目链接:http://acm.hnu.cn/online/?action=problem&type=show&id=12886&courseid=274
解题报告:输入4个数,要你判断用 + 、- 、 * 、/、四种运算能不能得到一个结果为24的式子,可以用括号。
解释一下测试的第四组样例:应该是6 / (1 - 3 / 4)
暴力枚举三种符号分别是什么,然后枚举这三种符号运算的顺序,然后枚举这四个数字的24种排列方式,时间是4^3 * 6 * 24
然后注意要用double型,判断是否等于24的时候要这样fabs(ans - 24.0) <= 0.000000001
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<map> 6 #include<string> 7 #include<cmath> 8 using namespace std; 9 int fu[4];10 int mei[50][5] = {11 {1 ,2 ,3 ,4},12 {1 ,2 ,4 ,3},13 {1 ,3 ,2 ,4},14 {1 ,3 ,4 ,2},15 {1 ,4 ,2 ,3},16 {1 ,4 ,3 ,2},17 {2 ,1 ,3 ,4},18 {2 ,1 ,4 ,3},19 {2 ,3 ,1 ,4},20 {2 ,3 ,4 ,1},21 {2 ,4 ,1 ,3},22 {2 ,4 ,3 ,1},23 {3 ,1 ,2 ,4},24 {3 ,1 ,4 ,2},25 {3 ,2 ,1 ,4},26 {3 ,2 ,4 ,1},27 {3 ,4 ,1 ,2},28 {3 ,4 ,2 ,1},29 {4 ,1 ,2 ,3},30 {4 ,1 ,3 ,2},31 {4 ,2 ,1 ,3},32 {4 ,2 ,3 ,1},33 {4 ,3 ,1 ,2},34 {4 ,3 ,2 ,1},35 };36 double CC(int f,double a,double b)37 {38 if(f == 4 && b == 0) return 0;39 if(f == 1) return a + b;40 if(f == 2) return a - b;41 if(f == 3) return a * b;42 if(f == 4) return a / b;43 }44 double calc(int l,double a,double b,double c,double d)45 {46 // double a = num[1],b = num[2],c = num[3],d = num[4];47 if(l == 1)48 return CC(fu[3],CC(fu[2],CC(fu[1],a,b),c),d);49 if(l == 2)50 return CC(fu[2],CC(fu[1],a,b),CC(fu[3],c,d));51 if(l == 3)52 return CC(fu[3],CC(fu[1],a,CC(fu[2],b,c)),d);53 if(l == 4)54 return CC(fu[1],a,CC(fu[3],CC(fu[2],b,c),d));55 if(l == 5)56 return CC(fu[2],CC(fu[1],a,b),CC(fu[3],c,d));57 if(l == 6)58 return CC(fu[1],a,CC(fu[2],b,CC(fu[3],c,d)));59 }60 int main()61 {62 63 int T;64 scanf("%d",&T);65 while(T--)66 {67 double num[5];68 scanf("%lf%lf%lf%lf",&num[1],&num[2],&num[3],&num[4]);69 int flag = 1;70 for(int i = 1;flag && i <= 4;++i)71 for(int j = 1;flag && j <= 4;++j)72 for(int k = 1;flag && k <= 4;++k)73 {74 fu[1] = i;75 fu[2] = j;76 fu[3] = k;77 for(int m = 0;flag && m < 24;++m)78 {79 for(int l = 1;flag && l <= 6;++l)80 {81 double ans = calc(l,num[mei[m][0]],num[mei[m][1]],num[mei[m][2]],num[mei[m][3]]);82 if(fabs(ans-24.0) <= 0.00000001)83 {84 flag = 0;85 break;86 }87 }88 }89 }90 printf(flag? "NO\n":"YES\n");91 }92 return 0;93 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。