本文主要是介绍uva 10317 - Equating Equations(dfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：uva 10317 - Equating Equations
题目大意：给出一个算式，然后有不大于100的若干个数，个数不大于16，符号不可以移动，找出成立的等式。
解题思路：一开始想用01背包去枚举组成sum/2的情况，但是WA了。后来用深搜枚举情况要么左边要么右边。
#include <stdio.h>
#include <string.h>const int N = 1605;
const int M = 20;
const int MAX = 1505;int nb, nc, num[M], l, r, sum, vis[M];
char op[M];void init(char str[]) {nb = nc = l = r = sum = 0;memset(num, 0, sizeof(num));memset(op, 0, sizeof(op));int len = strlen(str), k = 0;bool flag = true, isNum = true;for (int i = 0; i <= len; i++) {if (str[i] >= '0' && str[i] <= '9') {k = k * 10 + str[i] - '0';isNum = true;} else if ((str[i] == ' ' || str[i] == '\0') && isNum) {sum += k, num[nb++] = k;k = 0, isNum = false;} else {if (str[i] != ' ')op[nc++] = str[i];if (str[i] == '+') {flag ? l++ : r++;} else if (str[i] == '-') {flag ? r++ : l++;} else if (str[i] == '=') {flag = false;}}}l++, r++;
}bool dfs(int d, int s, int c) {if (d >= nb) {if (c == l && s == sum) return true;return false;}vis[d] = 0;if (dfs(d + 1, s, c)) return true;vis[d] = 1;if (s + num[d] > sum) return false;if (dfs(d + 1, s + num[d], c + vis[d])) return true;return false;
}bool solve() {if (sum % 2) return false;else sum /= 2;int numl[M], numr[M];if (dfs(0, 0, 0) == false) return false;int p = 0, q = 0;for (int i = 0; i < nb; i++) {if (vis[i]) numl[p++] = num[i];else numr[q++] = num[i];}p = q = 0;bool flag = true;printf("%d", numl[p++]);for (int i = 0; i < nc; i++) {if (op[i] == '=') {printf(" %c %d", op[i], numr[q++]);flag = false;} else {printf(" %c", op[i]);if (flag) {printf(" %d", op[i] == '+' ? numl[p++] : numr[q++]);} else {printf(" %d", op[i] == '-' ? numl[p++] : numr[q++]);}}}printf("\n");return true;
}int main () {char str[N];while (gets(str)) {init(str);if (solve() == false) printf("no solution\n");}return 0;
}
这篇关于uva 10317 - Equating Equations(dfs)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
