总时间限制: 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
代码（学自syx大佬）
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<cmath>#define LL long long#define p 0.00000001using namespace std;double num[5];bool f[5];bool dfs(int k)//计算完的卡号 { if(k==4){ for(int i=1;i<=4;i++) if(!f[i]&&fabs(num[i]-24.0)<p) return true; return false; } for(int i=1;i<=4;i++) if(!f[i]) for(int j=i+1;j<=4;j++) if(!f[j])//未计算过 { double tmp1=num[i],tmp2=num[j]; num[i]=tmp1+tmp2;f[j]=true; if(dfs(k+1)) return true; f[j]=false; num[i]=tmp1*tmp2;f[j]=true; if(dfs(k+1)) return true; f[j]=false; num[i]=tmp1-tmp2;f[j]=true; if(dfs(k+1)) return true; f[j]=false; num[i]=tmp2-tmp1;f[j]=true; if(dfs(k+1)) return true; f[j]=false; num[i]=tmp1/tmp2;f[j]=true; if(dfs(k+1)) return true; f[j]=false; num[i]=tmp2/tmp1;f[j]=true;//减或除以有两种情况 这是一个坑 if(dfs(k+1)) return true; f[j]=false; num[i]=tmp1;f[j]=false;//回溯 } return false;}int main(){ while(1){ memset(f,false,sizeof(f));//多组数据，每次初始化 scanf("%lf%lf%lf%lf",&num[1],&num[2],&num[3],&num[4]); if(num[1]==0&&num[2]==0&&num[3]==0&&num[4]==0) break; if(dfs(1)) PRintf("YES/n"); else printf("NO/n"); } return 0;}新闻热点
疑难解答
