首页 > 代码库 > Problem A: 速算24点

Problem A: 速算24点

2024-07-08 16:06:37   226人阅读

Description

速算24点相信绝大多数人都玩过。就是随机给你四张牌，包括 A(1),2,3,4,5,6,7,8,9,10,J(11),Q(12),K(13)。要求只用‘+‘,‘-‘,‘*‘,‘/‘运算符以及括号改变运算 顺序，使得最终运算结果为24(每张牌必须且仅能用一次)。游戏很简单，但遇到无解的情况往往让人很郁闷。你的任务就是针对每一组随机产生的四张牌，判断 是否有解。我们另外规定，整个计算过程中都不能出现小数。

Input

输入数据占一行，给定四张牌。

Output

如果有解则输出"Y"，无解则输出"N"。

Sample Input

A 2 3 6

Sample Output

Y

HINT

 

 核心算法
void dfs(int sum,int cur,int m){    if(flag)    return;    if(m==3)    {        if(sum+cur==24||sum-cur==24||sum*cur==24)        flag=1;        if(cur!=0&&sum%cur==0&&sum/cur==24)        flag=1;        return;    }    dfs(sum+cur,num[m+1],m+1);  //先计算前一部分    dfs(sum-cur,num[m+1],m+1);    dfs(sum*cur,num[m+1],m+1);    if(cur!=0&&sum%cur==0)    dfs(sum/cur,num[m+1],m+1);    dfs(sum,cur+num[m+1],m+1);  //先计算后一部分，相当于加括号    dfs(sum,cur-num[m+1],m+1);    dfs(sum,cur*num[m+1],m+1);    if(num[m+1]!=0&&cur%num[m+1]==0)    dfs(sum,cur/num[m+1],m+1);}

	qsort(num,4,sizeof(num[0]),cmp);	flag=0;	do	{		dfs(num[0],num[1],1);	}while(next_permutation(num,num+4)&&!flag);

dfs(a,b,m)代表着要将a和b作为两个数字，递归做算法。至于m那是标记在四张牌里一共用到了几张牌，用了三牌，就可以摊牌看结果了

next_permutation(num,num+4)这个有点屌，直接就是将num数组重新排序一下，简单了很多


联系
我们