题意:给出一个式子,但这个式子不一定是等式,在‘+’,‘-’符号位置不变的情况下,重新排列数字的位置,使其成为等式,如果可以的话,输出其中一种排列方式。
思路:我们将等号右边的数全部移动到等号右边,例如a+b-c=d-e,移动后变成a+b+e-(c+d)=0,也就是a+b+e=c+d,所以当式子可以变化成等式时,所有数的和必然是偶数。那么问题可以转化为在n个数中找出m个数(m的值为等号左边的整数的数量),使m个 数的和为从和的一半。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 1005; char str[MAXN], Lsy[MAXN], Rsy[MAXN], vis[MAXN]; int arr[MAXN], front[MAXN], back[MAXN]; int cnt1, cnt2, eql, Lnum, ans, flag, L, R; int init() { cnt1 = 1, cnt2 = eql = L = R = 0; int l = strlen(str), sum = 0; sscanf(str, "%d", &arr[0]); sum = arr[0]; for (int i = 0; i < l; i++) { if (str[i] == '+' || str[i] == '-' || str[i] == '=') { if (str[i] == '=') eql = i; if (!eql) { Lsy[L] = str[i]; L++; } else if (eql != i) { Rsy[R] = str[i]; R++; } sscanf(str + i + 1, "%d", &arr[cnt1]); sum += arr[cnt1++]; } } Lnum = 1; for (int i = 0; i < l; i++) { if (i < eql && str[i] == '+') Lnum++; else if (i > eql && str[i] == '-') Lnum++; } return sum; } int dfs(int k, int pos, int cur) { if (k == Lnum) { if (cur == ans) return true; return false; } if (Lnum - k > cnt1 - pos) return false; if (pos < cnt1 && cur + arr[pos] <= ans) { vis[pos] = 1; if (dfs(k + 1, pos + 1, cur + arr[pos])) return true; vis[pos] = 0; } if (pos < cnt1 && dfs(k, pos + 1, cur)) return true; return false; } void outPut() { int x = 0, y = 0; for (int i = 0; i < cnt1; i++) { if (vis[i]) front[x++] = arr[i]; else back[y++] = arr[i]; } printf("%d", front[--x]); for (int i = 0; i < L; i++) { printf(" %c ", Lsy[i]); if (Lsy[i] == '+') printf("%d", front[--x]); if (Lsy[i] == '-') printf("%d", back[--y]); } printf(" = "); printf("%d", back[--y]); for (int i = 0; i < R; i++) { printf(" %c ", Rsy[i]); if (Rsy[i] == '+') printf("%d", back[--y]); if (Rsy[i] == '-') printf("%d", front[--x]); } printf("\n"); } int main() { while (gets(str)) { int s = init(); if (s % 2) printf("no solution\n"); else { ans = s / 2; memset(vis, 0, sizeof(vis)); if (dfs(0, 0, 0)) outPut(); else printf("no solution\n"); } } return 0; }
UVA10317- Equating Equations(回溯+剪枝),布布扣,bubuko.com
UVA10317- Equating Equations(回溯+剪枝)
原文:http://blog.csdn.net/u011345461/article/details/38587595