题目大意
给出序列1 2 3 … n，在序列的每个数字之间可以决定是否插入符号“+”、“-”。输出所有结果等于0的式子。
思路
简单枚举，用广搜枚举所有情况即可。
代码
1 | /* |
2 | ID: lujunda1 |
3 | LANG: C++ |
4 | PROG: zerosum |
5 | */ |
6 | #include<iostream> |
7 | #include<stdio.h> |
8 | #include<cstring> |
9 | #include<queue> |
10 | using namespace std; |
11 |
12 | struct state |
13 | //结构体state用于存储式子。 |
14 | { |
15 | char str[20]; |
16 | }; |
17 |
18 | bool check(char* str,int n) |
19 | //判断式子str的结果是否为0。 |
20 | { |
21 | int len=n*2-1; |
22 | int sum=0,op=1,temp=1; |
23 | //sum式子临时的结果。 |
24 | //op当前运算数的符号。 |
25 | //temp当前运算数的大小。 |
26 | for(int i=1;i<len;i++) if(i%2)="" {="" if(str[i]="='" ')="" temp*="10;" continue;="" }="" sum+="temp*op;" op="str[i]=='+'?1:-1;" temp="0;" else="" temp+="str[i]-'0';" return="" sum+temp*op="=0?true:false;" temp*op为str的结果。="" void="" bfs(int="" n)="" queue<state=""> q; |
27 | state head; |
28 | head.str[0]='1'; |
29 | head.str[1]='\0'; |
30 | q.push(head); |
31 | int temp=1; |
32 | while(++temp<=n) |
33 | { |
34 | int size=q.size(); |
35 | while(size--) |
36 | { |
37 | head=q.front(); |
38 | q.pop(); |
39 | head.str[temp*2-3]=' '; |
40 | //按字典序，先' '，后'+'，最后'-'。 |
41 | head.str[temp*2-2]='0'+temp; |
42 | head.str[temp*2-1]='\0'; |
43 | q.push(head); |
44 | head.str[temp*2-3]='+'; |
45 | q.push(head); |
46 | head.str[temp*2-3]='-'; |
47 | q.push(head); |
48 | } |
49 | } |
50 | while(q.size()) |
51 | { |
52 | if(check(q.front().str,n)) |
53 | printf("%s\n",q.front().str); |
54 | q.pop(); |
55 | } |
56 | } |
57 |
58 | int main() |
59 | { |
60 | freopen("zerosum.in","r",stdin); |
61 | freopen("zerosum.out","w",stdout); |
62 | int n; |
63 | scanf("%d",&n); |
64 | bfs(n); |
65 | } |
66 | </len;i++)></queue></cstring></stdio.h></iostream> |
