首页 > 代码库 > 【DFS】算24点
【DFS】算24点
[tyvj2802/RQNOJ74]算24点
描述
几十年前全世界就流行一种数字游戏,至今仍有人乐此不疲.在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个1~9之间的自然数作为操作数,而您的任务是对这4个操作数进行适当的算术运算,要求运算结果等于24。
您可以使用的运算只有:+,-,*,/,您还可以使用()来改变运算顺序。注意:所有的中间结果须是整数,所以一些除法运算是不允许的(例如,(2*2)/4是合法的,2*(2/4)是不合法的)。下面我们给出一个游戏的具体例子:
若给出的4个操作数是:1、2、3、7,则一种可能的解答是1+2+3*7=24。计算过程:
2+1=3
7*3=21
21+3=24
本题不要求输出具体计算过程。
输入格式
只有一行,四个1到9之间的自然数。
输出格式
如果有解的话,只要输出“yes”。如果没有解则输出“no”。
注意:不要输出引号“”。
测试样例1
输入
1 2 3 7
输出
yes
试题分析:这道题看着简单,其实背后的反例要考虑周全。如:6 8 2 1:(6*8)/(2*1)=24
针对这种情况,我们要怎么办呢?难道用两个DFS合并为一个答案?
显然不是,只要用我们枚举到的a[i]/ans或a[i]-ans,a[i]*ans就可以了。(ans为当前DFS到的答案)
为什么这样做呢?这样单纯的a[i]/ans,那么上面那种两个组合相除的情况怎么办?
我们发现,当格式为上面的情况,我们只需要以8/(2*1)*6来DFS就好了
那万一a/(b*c)除不尽怎么办? 用double就好了……当DFS到最后一个时,会把它乘回整数的
代码:
#include<iostream>#include<cstring>#include<cstdio>#include<queue>#include<stack>#include<vector>#include<algorithm>//#include<cmath>using namespace std;const int INF = 9999999;#define LL long longinline int read(){ int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f;}int N,M;int a[5];char c;bool vis[5];bool t[5];double sum[40];bool aflag=false;void dfs(int st,double ans){ if(st==4&&ans==24){ puts("yes"); aflag=true; exit(0); } else if(st==4) return ; for(int i=1;i<=4;i++) t[i]=vis[i]; for(int i=1;i<=4;i++){ int tmp=4,su=0; if(vis[i]) continue; vis[i]=true; dfs(st+1,ans+a[i]); dfs(st+1,ans-a[i]); if(ans!=0) dfs(st+1,ans/a[i]); if(ans!=0) dfs(st+1,ans*a[i]); if(ans!=0&&a[i]>ans) dfs(st+1,a[i]/ans); if(sum[i]>ans) dfs(st+1,a[i]-ans); vis[i]=false; }}int main(){ //freopen(".in","r",stdin); //freopen(".out","w",stdout); for(int i=1;i<=4;i++){ cin>>c; if(c==‘A‘) a[i]=1; else if(c==‘J‘) a[i]=11; else if(c==‘Q‘) a[i]=12; else if(c==‘K‘) a[i]=13; else a[i]=c-‘0‘; } dfs(0,0); if(!aflag) puts("no"); return 0;}
【DFS】算24点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。