1790 - 2.3.3 file zerosum
描述
请考虑一个由1到N（N=3, 4, 5 ... 9）的数字组成的递增数列：1 2 3 ... N。 现在请在数列中插入“+”表示加，或者“-”表示减，“ ”表示空白(例如1-2 3就等于1-23)，来将每一对数字组合在一起（请不要在第一个数字前插入符号）。 计算该表达式的结果并判断其值是否为0。 请你写一个程序找出所有产生和为零的长度为N的数列。
格式
PROGRAM NAME: zerosum
INPUT FORMAT
单独的一行表示整数N (3 <= N <= 9)。
OUTPUT FORMAT
按照ASCII码的顺序，输出所有在每对数字间插入“+”, “-”, 或 “ ”后能得到结果为零的数列。
SAMPLE INPUT (file zerosum.in)
7
<span class="mw-headline" id="SAMPLE_OUTPUT_.28file_zerosum.out.29">SAMPLE OUTPUT (file zerosum.out)</span>
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
Input
Output
Examples
Input
Output
Solution C++
#include <iostream> #include <iomanip> #include <algorithm> #include <string> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #include <ctime> using namespace std; int N,sz[10],cunc[10000][10],coun=0; char zf[5]={'0',' ','+','-','\0'}; void caoz() { int i,j,sum=0,lins=1,fuh=1; for (i=1;i<N;i++) { if (sz[i]==1) lins=lins*10+i+1; else if (sz[i]==2) { if (fuh==1) sum+=lins; else sum-=lins; fuh=1; lins=i+1; } else if (sz[i]==3) { if (fuh==1) sum+=lins; else sum-=lins; fuh=0; lins=i+1; } } if (fuh==1) sum+=lins; else sum-=lins; if (sum==0) { for (i=1;i<=N;i++) cunc[coun][i]=sz[i]; coun++; } } void dfs(int x) { if (x==N) caoz(); else for (int i=1;i<=3;i++) { sz[x]=i; dfs(x+1); } } int main() { int i,j; scanf("%d",&N); dfs(1); for (i=0;i<coun;i++) { for (j=1;j<N;j++) printf("%d%c",j,zf[cunc[i][j]]); printf("%d\n",N); } return 0; }