問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2248思路:
第一個(gè)想法是BFS，不過(guò)習(xí)慣性地看discuss，發(fā)現(xiàn)大家用的都是DFS，于是還是用DFS+減枝
這道題目的關(guān)鍵減枝是: num[depth+1] = num[depth]+num[i], 0<=i<=depth，另外就是從大到小的搜索順序
另一種解法是迭代加深搜索，第一次使用，貌似就是用DFS實(shí)現(xiàn)BFS，不過(guò)空間需求與時(shí)間需求是兩者的折衷，其模板類似于:
1 for(deep=1; 1; deep++)
2
3 {
4
5 dfs(0);
6
7 If(find = true)
8
9 break;
10
11 }
代碼1:
1 #define MAX_LEN 101
2 #define INF 0x7FFFFFFF
3 int num[MAX_LEN];
4 int ans[MAX_LEN];
5 int n, min;
6
7 int
8 dfs(int depth)
9 {
10 int i, j;
11 if(depth+1 >= min)
12 return;
13 if(num[depth] == n) {
14 min = depth+1;
15 memcpy(ans, num, min*sizeof(int));
16 return;
17 }
18 for(i=depth; i>=0; i--)
19 if(num[i]+num[depth]<=n) {
20 num[depth+1] = num[i] + num[depth];
21 dfs(depth+1);
22 }
23 }
24
25 int
26 main(int argc, char **argv)
27 {
28 int i;
29 while(scanf("%d", &n)!=EOF && n!=0) {
30 min = INF;
31 num[0] = 1;
32 dfs(0);
33 for(i=0; i<min; i++)
34 printf("%d ", ans[i]);
35 printf("\n");
36 }
37 return 0;
38 }
代碼2:
1 #define MAX_LEN 101
2 int num[MAX_LEN];
3 int n, find, dplimit;
4
5 void
6 dfs(int depth)
7 {
8 int i, j;
9 if(depth >= dplimit)
10 return;
11 if(num[depth] == n) {
12 if(!find) {
13 for(j=0; j<=depth; j++)
14 printf("%d ", num[j]);
15 printf("\n");
16 find = 1;
17 }
18 return;
19 }
20 for(i=depth; i>=0; i--)
21 if(num[i]+num[depth]<=n) {
22 num[depth+1] = num[i] + num[depth];
23 dfs(depth+1);
24 }
25 }
26
27 int
28 main(int argc, char **argv)
29 {
30 while(scanf("%d", &n)!=EOF && n!=0) {
31 find = 0;
32 num[0] = 1;
33 for(dplimit=1; 1; dplimit++) {
34 dfs(0);
35 if(find)
36 break;
37 }
38 }
39 }