题目描述
几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲．在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个1~9之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算，要求运算结果等于24。
您可以使用的运算只有：+，-，*，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，(2*2)/4是合法的，2*(2/4)是不合法的）。下面我们给出一个游戏的具体例子：
若给出的4个操作数是：1、2、3、7，则一种可能的解答是1+2+3*7=24。
输入输出格式
输入格式：
只有一行，四个1到9之间的自然数。
输出格式：
如果有解的话，只要输出一个解，输出的是三行数据，分别表示运算的步骤。其中第一行是输入的两个数和一个运算符和运算后的结果，第二行是第一行的结果和一个输入的数据、运算符、运算后的结果，或者是另外两个数的输出结果；第三行是前面的结果第二行的结果或者剩下的一个数字、运算符和“=24”。如果两个操作数有大小的话则先输出大的。
如果没有解则输出“No answer!”
如果有多重合法解，输出任意一种即可。
注：所有运算结果均为正整数
输入输出样例
1 2 3 7
2+1=3 7*3=21 21+3=24
说明
感谢chenyy提供special judge
分析：很显然，这是一道爆搜的题,关键就是看哪一种搜索的方式容易写，不会错.
1.我们可以搜每个符号的位置，这样的话要判断是否合法，并且要在栈里面进行运算，超级麻烦.
2.考虑能不能省去括号，其实是可以的，因为括号的作用无非就是改变运算顺序，我们只需要每次枚举哪两个数运算就好了.
3.如果用上面那种方法，那么我们也不需要用栈处理了，因为所有的运算顺序都被枚举到了.
接下来是输出的问题，只需要输出3个式子，在每次计算的时候记录一下第i次计算的数字和符号就好了。我本来想用第一种方法，题解中第二种方法很好，学习了.正所谓多一层枚举，少一点编程复杂度.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> using namespace std; int d[5][5],ans[5][3],fuhao[5]; int jisuan(int x,int y,int op) { if (op == 1) return x + y; if (op == 2) return x - y; if (op == 3) return x * y; if (op == 4) return x / y; } char zhuanhuan(int k) { if (k == 1) return '+'; if (k == 2) return '-'; if (k == 3) return '*'; if (k == 4) return '/'; } void print() { for(int i = 4; i >= 2; i--) printf("%d%c%d=%d ",ans[i][1],zhuanhuan(fuhao[i]),ans[i][2],d[i - 1][1]); exit(0); } void dfs(int dep) { if (dep == 1) { if (d[1][1] == 24) print(); return; } for (int i = 1; i <= dep; i++) for (int j = 1; j <= dep; j++) if (i != j) { for (int k = 1; k <= 4; k++) { /* 1 --- + 2 --- - 3 --- * 4 --- / */ if ((k == 2 && d[dep][i] <= d[dep][j]) || (k == 4 && d[dep][j] != 0 && d[dep][i] % d[dep][j] != 0)) continue; ans[dep][1] = max(d[dep][i],d[dep][j]); ans[dep][2] = min(d[dep][i],d[dep][j]); fuhao[dep] = k; int cnt = 0; d[dep - 1][++cnt] = jisuan(d[dep][i],d[dep][j],k); for (int l = 1; l <= dep; l++) if (l != i && l != j) d[dep - 1][++cnt] = d[dep][l]; dfs(dep - 1); } } } int main() { for (int i = 1; i <= 4; i++) scanf("%d",&d[4][i]); dfs(4); printf("No answer!"); return 0; }