时间限制 1000ms 空间限制 65536K
题目描述
请考虑一个被空格分隔的，由1到N的整数组成的递增数列：1 2 3 ... N。现在请在数列中插入表示加的“+”，或者表示减“-”，亦或者表示空白的“ ”(例如1-2 3就等于1-23)，来将每一对数字组合成一个表达式（第一个数字前无空格）。计算该表达式的结果并判断其值是否为0。请你写一个程序找出所有产生和为零的长度为N的数列。
输入为一行，包含一个整数N（3≤N≤9）。
输出为所有在每对数字间插入“+”, “-”,或 “ ”后能得到和为零的数列，并按照字典（ASCII码）序排列。
样例输入
7
样例输出
1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7
【思路】
数据很小，暴力枚举即可，按照字典序从小到大枚举即从前往后按先放空格，再放加号，最后放减号的顺序枚举，递归结束时计算并判断表达式值是否为零，为零做输出即可。就是一定要注意字符串结尾的那个’\0’千万别忘了。
#include#include #include #include #include using namespace std;int n, i, j;char gap[50];char cpy[50];int calc() { int len = 0; for (int i = 0; i < j; i++) { if (' ' != gap[i]) cpy[len++] = gap[i]; } cpy[len] = '\0';//因为这句忘写了，结果错误，检查了好半天，打代码细心还是很重要的 int ans = 0, tmp = 1, i = 0; while (i < len) { ans += tmp*atoi(cpy + i); while (isdigit(cpy[i])) i++; tmp = cpy[i] == '+' ? 1 : -1; i++; } return ans;}void solve(int k) { if (k == j) { if (0 == calc()) printf("%s\n", gap); return; } gap[k] = ' '; solve(k + 2); gap[k] = '+'; solve(k + 2); gap[k] = '-'; solve(k + 2);}int main() { while (scanf("%d", &n) == 1) { memset(gap, 0, sizeof(gap)); memset(cpy, 0, sizeof(cpy)); for (i = 1, j = 1; i <= n; i++, j += 2) { gap[j - 1] = i + 48; if (j == 2 * n - 1) break; } solve(1); } return 0;}