本文主要是介绍hdu1427,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
速算24点
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 2868 Accepted Submission(s): 685
Problem Description
速算24点相信绝大多数人都玩过。就是随机给你四张牌,包括A(1),2,3,4,5,6,7,8,9,10,J(11),Q(12),K(13)。要求只用'+','-','*','/'运算符以及括号改变运算顺序,使得最终运算结果为24(每个数必须且仅能用一次)。游戏很简单,但遇到无解的情况往往让人很郁闷。你的任务就是针对每一组随机产生的四张牌,判断是否有解。我们另外规定,整个计算过程中都不能出现小数。
Input
每组输入数据占一行,给定四张牌。
Output
每一组输入数据对应一行输出。如果有解则输出"Yes",无解则输出"No"。
Sample Input
A 2 3 6 3 3 8 8
Sample Output
Yes No
Author
LL
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a[4];
bool ok = false;void dfs(int value1, int value2, int cur){if(ok){return;}if(cur==3){if(value1+value2==24||value1-value2==24||value1*value2==24||(value2&&value1%value2==0&&value1/value2==24)){ok = true;}return;}dfs(value1+value2, a[cur+1], cur+1);dfs(value1, value2+a[cur+1], cur+1);dfs(value1-value2, a[cur+1], cur+1);dfs(value1, value2-a[cur+1], cur+1);dfs(value1*value2, a[cur+1], cur+1);dfs(value1, value2*a[cur+1], cur+1);if(value2&&value1%value2==0){dfs(value1/value2, a[cur+1], cur+1);}if(a[cur+1]&&value2%a[cur+1]==0){dfs(value1, value2/a[cur+1], cur+1);}
}int main(){freopen("in.txt", "r", stdin);char c[2];while(scanf("%s", c)!=EOF){if(strlen(c)==2){a[0] = 10;}else if(c[0]=='A'){a[0] = 1;}else if(c[0] == 'J'){a[0] = 11;}else if(c[0]=='Q'){a[0] = 12;}else if(c[0]=='K'){a[0] = 13;}else{a[0] = int(c[0]-'0');}for(int i = 1; i<4; i++){scanf("%s", c);if(strlen(c)==2){a[i] = 10;}else if(c[0]=='A'){a[i] = 1;}else if(c[0] == 'J'){a[i] = 11;}else if(c[0]=='Q'){a[i] = 12;}else if(c[0]=='K'){a[i] = 13;}else{a[i] = int(c[0]-'0');}}sort(a, a+4);ok = false;do{dfs(a[0],a[1],1); }while(!ok&&next_permutation(a, a+4));if(ok){printf("Yes\n");}else{printf("No\n");}}return 0;
}
参考了http://blog.csdn.net/cambridgeacm/article/details/7751678
http://blog.csdn.net/kkkwjx/article/details/12939775
这篇关于hdu1427的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!