速算24点的小窍门,速算24点万能口诀

题目描述

速算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