本文主要是介绍uva10400 - Game Show Math(回溯+剪枝),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:uva10400 - Game Show Math(回溯+剪枝)
题目大意:给出N个数,并且给出一个目标数值,要求用上面的数字(全部),并且顺序不能乱,然后用+-*/这些操作,问最终能不能得到目标数值。这里要注意给出的数会在【-32000,32000】之间, 并且要用除法的时候,只有在能整除的时候才能用。并且中间计算结果不能超过【-32000,32000】范围。如果超过这个操作不能做。
解题思路:回溯加剪枝,将每一层计算的结果都保存下来,如果在同一层发现值出现过,并且之前计算发现这样往后是得不到目标值的,那么就可以直接剪掉。
这题题意没有读清楚,结果WA了好多遍。
代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>const int N = 105;
const int M = 70000;
const int maxn = 32000;char op[N];
int num[N];
int n;
int target;
int flag;
char OP[4] = {'*', '-', '+', '/'};
int vis[N][M];void dfs (int k, int sum) {if (k == n - 1) {/* for (int i = 0; i < n - 1; i++)printf ("%c ", op[i]);printf ("\n");printf ("%d\n", sum);*/if (sum == target)flag = 1;return;}int temp;for (int i = 0; i < 4; i++) {op[k] = OP[i]; switch (OP[i]) {case '+' : temp = sum + num[k + 1];if (abs (temp) > maxn)break;if (vis[k][temp + maxn])break;dfs (k + 1, temp); break;case '-' : temp = sum - num[k + 1];if (abs (temp) > maxn)break;if (vis[k][temp + maxn])break;dfs (k + 1, temp); break;case '/' : if (sum % num[k + 1] == 0) {temp = sum / num[k + 1];if (abs (temp) > maxn)break;if (vis[k][temp + maxn])break;dfs (k + 1, temp); }break;case '*' : temp = sum * num[k + 1];if (abs (temp) > maxn)break;if (vis[k][temp + maxn])break;dfs (k + 1, temp); break;}if (flag)return;else if (abs (temp) <= maxn && !vis[k][temp + maxn])vis[k][temp + maxn] = 1;}
}int main () {int t;scanf ("%d", &t);while (t--) {scanf ("%d", &n);for (int i = 0; i < n; i++)scanf ("%d", &num[i]);scanf ("%d", &target);flag = 0;memset (vis, 0, sizeof (vis));dfs(0, num[0]);
// printf("%d\n", flag);if (!flag)printf ("NO EXPRESSION\n");else {for (int i = 0; i < n; i++) {if (i == n - 1)printf ("%d=%d\n", num[i], target);elseprintf ("%d%c", num[i], op[i]);}}}return 0;
}
这篇关于uva10400 - Game Show Math(回溯+剪枝)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!