Time Limit: 1 second
Memory Limit: 32 MB
【问题描述】
几十年前全世界就浒一种数字游戏，至今仍有人乐此不疲。在中国我们把这种游戏称为“算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
【题解】
搜索的策略是，这4个数字只进行三次运算。
我们只需要在搜索里加两个变量就可以了（int 当前算式的和，int 当前进行了几次运算）
然后加括号的问题，可以用全排列的方法解决。即把所有的数字和运算符的组合方式表示出来。然后看它
们的和是否为24.
运算次数==4的时候，判断一下和是否为24.如果是就输出。
注意在进行减法和除法之前。要先判断一下a是否大于b，如果不是，则需要调换顺序再减。注意不是看到
a<b就直接跳过了，而是更换一下它们的数字再减。这是个坑点。
【代码】
#include <cstdio> #include <stdlib.h> int a[5],num[4][2],ans[4]; bool bo[5]; char sym[4]; void input_data() { for (int i = 1;i <= 4;i++) //bo数组用来判断哪一些数字可以用，一开始全部可用 bo[i] = true; for (int i = 1;i <= 4;i++) //输入4个数字 scanf("%d",&a[i]); } void sear_ch(int now,int p) //当前算式的和为now，且进行到第p步运算 { if (p > 3) { if (now == 24) //如果已经进行完3次运算 且和为24 { for (int i = 1;i <= 3;i++) //输出3次运算的算式 { int aa = num[i][0],bb = num[i][1]; if ( num[i][1] > num[i][0]) //大的靠前输出 a[0] = aa,aa = bb,bb = a[0]; printf("%d",aa); putchar(sym[i]); printf("%d=%d ",bb,ans[i]); } exit(0); } return; } for (int i = 1;i <= 4;i++) //找下一个可以用来运算的数字 if (bo[i]) { int x = now,y = a[i]; //这是在做除法和减法的时候a < b的情况的特殊处理 if (x < y) { int t = x; x = y; y =t ; } bo[i] = false; num[p][0] = x; num[p][1] = y; //plus sym[p] = '+'; //plus运算则不需要调换顺序 ans[p] = now+a[i]; //其实这里可以用x,y代替。这样最后就不用判断那一个大了。 sear_ch(now+a[i],p+1); //subtract sym[p] = '-'; //subtract运算则需要 x > y，且一开始如果now < a[i] //不能跳过，而要调换顺序然后再做减法 ans[p] = x-y; sear_ch(x-y,p+1); //multiply sym[p] = '*'; //multiply运算则不必管大小 ans[p] = now*a[i]; sear_ch(now*a[i],p+1); //division if (y != 0 && x % y == 0) //如果能够整除则可以除。因为有说不能出现分数。 { sym[p] = '/'; ans[p] = x / y; sear_ch(x/y,p+1); } bo[i] = true; } } void get_ans() { for (int i = 1;i <= 4;i++) //全排列。 { bo[i] = false; sear_ch(a[i],1); bo[i] = true; } } int main() { //freopen("F:\rush.txt","r",stdin); input_data(); get_ans(); printf("No answer!"); //最后要记得输出无解信息。 return 0; }