Zero Sum
Consider the sequence of digits from 1 through N (where N=9) in increasing order: 1 2 3 … N.
Now insert either a ‘+’ for addition or a ‘-‘ for subtraction or a ‘ ‘ [blank] to run the digits together between each pair of digits (not in front of the first digit). Calculate the result that of the expression and see if you get zero.
Write a program that will find all sequences of length N that produce a zero sum.
PROGRAM NAME: zerosum
INPUT FORMAT
A single line with the integer N (3 <= N <= 9).
SAMPLE INPUT (file zerosum.in)
7
OUTPUT FORMAT
In ASCII order, show each sequence that can create 0 sum with a ‘+’, ‘-‘, or ‘ ‘ between each pair of numbers.
SAMPLE OUTPUT (file zerosum.out)
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
USACO_2.3-3:zerosum零的算式和
Time Limit:1000MS Memory Limit:65536K
Total Submit:6 Accepted:4
Description
请考虑一个由1到N（N=3, 4, 5 … 9）的数字组成的递增数列：1 2 3 … N。现在请在数列中插入“+”表示加，或者“-”表示减，抑或是“ ”表示空白，来将每一对数字组合在一起（请不在第一个数字前插入符号）。计算该表达式的结果并注意你是否得到了和为零。请你写一个程序找出所有产生和为零的长度为N的数列。
Input
PROGRAM NAME: zerosum
单独的一行表示整数N (3 <= N <= 9)。
Output
按照ASCII码的顺序，输出所有在每对数字间插入“+”, “-”, 或 “ ”后能得到和为零的数列。
Sample Input
7
Sample Output
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
========================= 华丽的分割线 =========================
一个DFS, 题目说了按ASCII的顺序进行输出, 也就是先’ ‘, 再’+’, 接着’-‘.., 我拿到题目就写了一个程序,, DFS没写错, 就是算和的时候错了. 试着写了几个版本, 都错了..(看样子我还是不怎么滴啊~~ 狂汗”).
不说多的废话了, 代码贴上来:
/*
LANG: C
ID: zqy11001
PROG: zerosum
*/
#include <stdio.h>
#define getint(i) scanf(%d, &i)
#define putint(i) printf(%d, i)
#define ze(now, c) str[now] = c; zero(now + 1);
#define MAX 200
int n;
char str[9];
void out(void)
{
int i;
putchar(\'1\');
for(i = 1; i < n; i++){
printf(%c%d, str[i], i + 1);
}
putchar(\'\\n\');
}
void zero(int sum, int t, int now, char s)
{
if(now == n){
if(s == \'+\'){
sum += t;
}else{
sum -= t;
}
if(sum == 0 && str[0] == \'+\'){
out();
}
return;
}
str[now] = \' \';
zero(sum, t * 10 + now + 1, now + 1, s);
if(s == \'+\'){
sum += t;
}else{
sum -= t;
}
str[now] = \'+\';
zero(sum, now + 1, now + 1, \'+\');
str[now] = \'-\';
zero(sum, now + 1, now + 1, \'-\');
}
int main(void)
{
int i, j;
freopen(zerosum.in, r, stdin);
freopen(zerosum.out, w, stdout);
getint(n);
zero(0, 0, 0, \'+\');
return 0;
}