HDU 1427 速算24点-DFS
Related: Compute 24 每日一题(13)――24点 (分治&递归)
http://java-mans.iteye.com/blog/1642726
https://moonstonelin.wordpress.com/2016/04/06/caculate-24/
http://www.voidcn.com/blog/u014664226/article/p-4336216.html
Related: Compute 24 每日一题(13)――24点 (分治&递归)
速算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
枚举数字和运算符，DFS即可，注意题目要求计算过程中都不能出现小数，所以做除法时稍作处理
枚举数组可用algorithm里的next_permutation
The next_permutation() function attempts to transform the given range of elements [start,end) into the next lexicographically greater permutation of elements. If it succeeds, it returns true, otherwise, it returns false.
http://www.xuebangwang.com/article-7594-1.htmlvoid dfs(int sum,int next,int p) //表示当前已经算出的值是sum，括号中算出的值是next,当前使用的卡片下标为p { if(p==4) //正在用第4张牌 { if(sum+next==24||sum-next==24||sum*next==24) flag=true; if(next!=0&&sum%next==0&&sum/next==24) flag=true; return; } //1、不加括号 dfs(sum+next,cardNum[p+1],p+1); dfs(sum-next,cardNum[p+1],p+1); dfs(sum*next,cardNum[p+1],p+1); if(next!=0&&sum%next==0) dfs(sum/next,cardNum[p+1],p+1); //2、加括号，则需要改变运算顺序 dfs(sum,next+cardNum[p+1],p+1); dfs(sum,next-cardNum[p+1],p+1); dfs(sum,next*cardNum[p+1],p+1); if(cardNum[p+1]!=0&&next%cardNum[p+1]==0) dfs(sum,next/cardNum[p+1],p+1); }
http://blog.csdn.net/u014492609/article/details/40268385sort(cardNum+1,cardNum+5); do { dfs(cardNum[1],cardNum[2],2); }while(!flag&&next_permutation(cardNum+1,cardNum+5));
http://java-mans.iteye.com/blog/1642726
- int num[4];
- int cmp(const void *a,const void *b)
- {
- return *(int *)a-*(int *)b;
- }
- 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);
- if(flag)
- printf("Yes\n");
- else
- printf("No\n");
https://moonstonelin.wordpress.com/2016/04/06/caculate-24/
public List<string> Generate24(int[] cards){ List<string> result = new List<string>(); Dictionary<string, int> dict = GenerateHelper(cards); foreach (var kp in dict) { if (!result.Contains(kp.Key) && (kp.Value == 24)) { result.Add(kp.Key); } } return result;}private Dictionary<string, int> GenerateHelper(int[] cards){ Dictionary<string, int> dict = new Dictionary<string, int>(); if (cards.Length == 1) { dict.Add(cards[0].ToString(), cards[0]); } if (cards.Length == 2) { this.AddEntries(dict, cards[0].ToString(), cards[1].ToString(), cards[0], cards[1]); } if (cards.Length == 3) { List<int> cards1 = new List<int>(); List<int> cards2 = new List<int>(); for (int i = 0; i <= 2; i++) { Swap(cards, 0, i); Dictionary<string, int> dict1 = GenerateHelper(new int[]{ cards[0] }); Dictionary<string, int> dict2 = GenerateHelper(new int[] { cards[1], cards[2] }); this.Construct(dict, dict1, dict2); } } if (cards.Length == 4) { List<int> cards1 = new List<int>(); List<int> cards2 = new List<int>(); for (int i = 0; i <= 3; i++) { Swap(cards, 0, i); Dictionary<string, int> dict1 = GenerateHelper(new int[] { cards[0] }); Dictionary<string, int> dict2 = GenerateHelper(new int[] { cards[1], cards[2], cards[3] }); this.Construct(dict, dict1, dict2); } for (int i = 0; i <= 3; i++) { for (int j = i + 1; j <= 3; j++) { Swap(cards, 0, i); Swap(cards, 1, j); Dictionary<string, int> dict1 = GenerateHelper(new int[] { cards[0], cards[1] }); Dictionary<string, int> dict2 = GenerateHelper(new int[] { cards[2], cards[3] }); this.Construct(dict, dict1, dict2); } } } return dict;}private void Swap(int[] input, int i, int j){ int tmp = input[i]; input[i] = input[j]; input[j] = tmp;}private void Construct(Dictionary<string, int> dict, Dictionary<string, int> dict1, Dictionary<string, int> dict2){ foreach (var kp1 in dict1) { foreach (var kp2 in dict2) { this.AddEntries(dict, kp1.Key, kp2.Key, kp1.Value, kp2.Value); } }}private void AddEntries(Dictionary<string, int> dict, string k1, string k2, int v1, int v2){ if (!dict.ContainsKey("(" + k1 + "+" + k2 + ")")) { dict.Add("(" + k1 + "+" + k2 + ")", v1 + v2); } if (!dict.ContainsKey("(" + k1 + "-" + k2 + ")")) { dict.Add("(" + k1 + "-" + k2 + ")", v1 - v2); } if (!dict.ContainsKey("(" + k1 + "*" + k2 + ")")) { dict.Add("(" + k1 + "*" + k2 + ")", v1 * v2); } if ((v2 != 0) && !dict.ContainsKey("(" + k1 + "/" + k2 + ")")) { dict.Add("(" + k1 + "/" + k2 + ")", v1 / v2); }} |
int oper(int i, int m, int n) { //枚举四种运算符
if(i == 1) return m + n;
if(i == 2) return m - n;
if(i == 3) return m * n;
if(n == 0 || m % n != 0) return INF;
else return m / n;
}
bool calcu1(int i, int j, int k) { //计算顺序1 ((a@b)@c)@d
int tmp1 = oper(i, a[0], a[1]);
int tmp2 = oper(j, tmp1, a[2]);
int tmp3 = oper(k, tmp2, a[3]);
if(tmp3 == 24 || tmp3 == -24) return true;
return false;
}
bool calcu2(int i, int j, int k) { //计算顺序2 (a@b)@(c@d)
int tmp1 = oper(i, a[0], a[1]);
int tmp2 = oper(k, a[2], a[3]);
int tmp3 = oper(j, tmp1, tmp2);
if(tmp3 == 24 || tmp3 == -24) return true;
return false;
}
sort(a, a+4);
do {
for(int i = 1; i <= 4; i++)
for(int j = 1; j <= 4; j++)
for(int k = 1; k <= 4; k++) {
if(calcu1(i, j, k) || calcu2(i, j, k)) flag = 1;
}
} while(next_permutation(a, a+4) && !flag);
