前置知识：迭代加深搜索
定义
迭代加深是一种 每次限制搜索深度的 深度优先搜索。——OI Wiki
简单而言，就是一种限制搜索深度的DFS。有什么变化？？
过程
设搜索深度上限为 $h$，搜索深度为 $p$ 。
那么 $h$ 从 $1$ 开始自增，并在每次自增前进行DFS。（形如 dfs(p,h,...)）
当DFS函数内部检测到 $p\ge h$ 时，便结束递归，无论是否已经找到答案。
当所有递归结束后，如果找到了答案，那自然是最好的；否则使得 $h\leftarrow h+1$ 后再次调用DFS从 $p=1$ 开始递归，直至找到答案。
DFS实现的BFS？
当搜索树的分支比较多时，每增加一层的搜索复杂度会出现指数级爆炸式增长，这时前面重复进行的部分所带来的复杂度几乎可以忽略，这也就是为什么迭代加深是可以近似看成 BFS 的。
也可以这么说。
但是需要注意的是，迭代加深搜索与广度优先搜索的思想完全不一样，这么说仅仅是因为上述原因。
为什么不使用BFS？
因为BFS会 $\text{MLE}$。
正解：迭代加深搜索+剪枝
每次限制序列长度 $m$ ，当 $dfs(p,h)$ 满足 $p>h$ 时，判断 $a_m$ 是否等于 $n$ 即可。
但需要注意的是，迭代加深搜索仍然摆脱不了搜索指数级的时间复杂度。因此，考虑剪枝。
-
限制搜索深度，这没什么好说的。
-
考虑到，假设第 $i$ 项为 $a_i$，那么 $a_{i+1}$ 最大为 $a_i+a_i=2\times a_i$，$a_{i+2}$ 最大为 $a_{i+1}+a_{i+1}=2\times a_{i+1}=4\times a_{i}$，一直到 $a_m$ 最大为 $2^{m-i}\times a_{i}$。
那么当我们在 $dfs(p,h)$ 枚举 $a_p$ 时，便可以加上剪枝：
if((a[p]<<(h-p))<n)return; -
枚举 $i,j<p$，使得 $a_p=a_i+a_j$，为了使得 $a_m$ 快速达到 $n$，我们从大到小遍历。即：$i$ 从 $p-1$ 到 $1$ 遍历，$j$ 从 $i$ 到 $1$ 遍历。
然后，需要特判 $n=0$ 和 $n=1$，$m$ 遍历 $2\sim n$。$m=n$ 时一定有解，因为那种情况就是对于整数 $i\in[2,n]$，满足 $a_i=a_{i-1}+1$。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=10000;
bool flag;
int n,a[N+1]={0,1};//a[1]=1
void dfs(int p,int h){
if(p>h){
if(a[h]==n)flag=true;
return;
}
for(int i=p-1;i>=1;i--){
for(int j=i;j>=1;j--){
a[p]=a[i]+a[j];
if((a[p]<<(h-p))<n)return;//位运算，常数优化
dfs(p+1,h);
if(flag)return;
}
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
while(true){
scanf("%d",&n);
if(n==0)return 0;
if(n==1){
printf("1\n");
continue;
}
for(int m=2;m<=n;m++){
flag=false;
dfs(2,m);
if(flag){
for(int j=1;j<i;j++)printf("%d ",a[j]);
printf("%d",a[i]);
putchar(10);
break;
}
}
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
