首页 > 代码库 > Problem A: 速算24点
Problem A: 速算24点
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数组重新排序一下,简单了很多
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。