首页 > 代码库 > 【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点