题意:
速算24点相信绝大多数人都玩过。就是随机给你四张牌,包括A(1),2,3,4,5,6,7,8,9,10,J(11),Q(12),K(13)。要求只用'+','-','*','/'运算符以及括号改变运算顺序,使得最终运算结果为24(每个数必须且仅能用一次)。游戏很简单,但遇到无解的情况往往让人很郁闷。你的任务就是针对每一组随机产生的四张牌,判断是否有解。我们另外规定,整个计算过程中都不能出现小数。
解法:DFS+回溯。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>using namespace std;
int num[4];void trans(string s,int i)
{if(s.size()==2)num[i]=10;elseswitch (s[0]){case 'A':num[i]=1;break;case 'J':num[i]=11;break;case'Q':num[i]=12;break;case'K':num[i]=13;break;default:num[i]=s[0]-'0';break;}
}bool dfs(int n)
{if(n==1) return num[0]==24;;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)//任意挑两个 避免了处理括号问题,和全排列。{int a=num[i],b=num[j];num[j]=num[n-1];//i放挑出来两个数的运算结果,j放最后元素。压缩数组num[i]=a+b;if(dfs(n-1))return 1;num[i]=a-b;if(dfs(n-1))return 1;num[i]=b-a;if(dfs(n-1))return 1;num[i]=a*b;if(dfs(n-1))return 1;if(b&&a%b==0){num[i]=a/b; if(dfs(n-1))return 1;}if(a&&b%a==0){num[i]=b/a;if(dfs(n-1))return 1;}num[i]=a;num[j]=b;//回溯}return 0;
}int main()
{string s;while(cin>>s){trans(s,0);for(int i=1; i<4; i++){cin>>s;trans(s,i);}if(dfs(4))cout<<"Yes"<<endl;else cout<<"No"<<endl;}}