题目描述
速算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 就是深搜 是一个四叉树 每一个数和下一个数进行加减乘除 除的话还要判断是否整除 整除才能进行 深搜 对深搜有了进一步的理解 因为在第一次加的时候 递归返回的已经是到第四层的操作 flag有可能已经为1了 所以下面的减的操作 就不必再进行了 否则会改变掉flag 因此每次做 都要进行flag的判断 体会很深刻啊 思考了两天 幸好有神犇的帮助
下面贴上AC的代码 每一个的全排列都要进行深搜
#include<stdio.h>#include<iostream>#include<algorithm>using namespace std;int flag;char a[4];int b[4];//搜索到第4层的时候 进行判断 如果没有到第4层的话 就加减乘除这一层的数void dfs(int cur,int zhi) { if(cur==4) { if(zhi==24) flag=1; else flag=0; return; } else { dfs(cur+1,zhi+b[cur+1]); if(flag) return; dfs(cur+1,zhi-b[cur+1]); if(flag) return; dfs(cur+1,zhi*b[cur+1]); if(flag) return; if(cur<=2 && zhi % b[cur+1] == 0) { dfs(cur+1,zhi/b[cur+1]); if(flag) return; } }}int main() { for(int i=0;i<4;i++) { cin>>a[i]; if(a[i]==’A’) b[i]=1; else if(a[i]==’J’) b[i]=11; else if(a[i]==’Q’) b[i]=12; else if(a[i]==’K’) b[i]=13; else b[i]=a[i]-‘0’; } flag=0; //全排列 总共24中情况的话 每种都做下来 随后进行深搜 有一种情况遇到即可 sort(b, b+4); do{ dfs(0,b[0]); }while(next_permutation(b,b+4)&&!flag); if(flag) cout<<“Y”<<endl; else cout<<“N”<<endl; return 0;}
针对全排列的算法，一种是可以直接用STL中的next_permutation算法，还有一种是可以递归或者非递归的实现，递归就是拆分，4个可以变成3个的全排列 3个可以变成2个的全排列 就这样一直做下去就好了 非递归的话就有点难了 先填上代码吧
#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<stdlib.h>using namespace std;//用于计算总共有多少种全排列int count;//进行交换的函数void swap(int *a, int *b) {int *c;c = a;a = b;b = c;}//用于计算总共有多少种全排列int cnt;//递归操作的函数 主要用来全排列的实现void permutation(int a[], int k, int m) {int i, j;if (k == m) {cnt++;}else{for (j = k; j < m; j++) {swap(&a[j], &a[k]);permutation(a, k + 1, m);//记住一定要再换回来swap(&a[j], &a[k]);}}}int main() {int *a, n, m, i, j;cin >> n;a = (int *)malloc(n*sizeof(int));for (i = 0; i < n; i++)cin >> a[i];cnt = 0;permutation(a, 0, n);cout << cnt;return 0;}非递归的代码
#include < stdio.h>#include < stdlib.h>int x[6]= {1,2,3,4,5,6};void printX(){ int i = 0; for(i=0;i<6;i++) printf(“%d “,x[i]); printf(“\n”);}int hasNext(){ int m = 5,i; for(i=m;i>0;i–) if(x[i]>x[i-1]) return 1; return 0;}void next(){ int i = 0;int top,mm; int tmp; //找到峰值 for (i=5;i>0;i–)if(x[i] > x[i-1]){top = i;break;} //找到交换的数，大于峰值前一个数的 最小的数 mm = top; for (i=top+1;i<6;i++) if(x[i]<x[top-1]){mm=i-1;break;} tmp = x[top-1]; x[top-1] = x[mm]; x[mm] = tmp; //颠倒后面的数 for(i=0;i<=(top+5)/2-top;i++){ tmp = x[i+top]; x[i+top] = x[5-i]; x[5-i] = tmp; }}int main(int argc,char *argv[]){ printX(); while (hasNext()) { next(); printX(); } return 0;}
具体可以看这个博客
http://www.cnblogs.com/answeryi/archive/2011/10/12/2209058.html