//// main.cpp// 529//// Created by Fangpin on 15/3/14.// Copyright (c) 2015年 FangPin. All rights reserved.//#include <iostream>#include <cstring>using namespace std;int a[10005]={1,2},n;bool ok;void dfs(int limit,int d){if(d==limit+1){if(a[limit]==n){//printf("%d %d",n,d);ok=true;for(int i=0;i<d;++i){if(i) printf(" ");printf("%d",a[i]);}printf("\n");}return ;}if((a[d-1]<<(limit-d+1))<n) return;for(int i=d-1;i>=0 && !ok;–i){for(int j=d-1;j>=i && !ok;–j){if(a[i]+a[j]<=a[d-1]) break;a[d]=a[i]+a[j];dfs(limit,d+1);}}}int main(int argc, const char * argv[]) {// insert code here…// freopen("out.txt","w",stdout);// for(n=1;n<=10000;++n){while(scanf("%d",&n),n){if(n==1)puts("1");else if(n==2)puts("1 2");else{for(int i=2;i<=n;++i){ok=false;dfs(i,2);if(ok){break;}}}}return 0;}题目大意：
给一个数字n， 然后输出一个元素个数最少的从1到n的序列（可能有多种方案，输出其中一种即可）。
其中对于第k个数Ak， 它的值等于Ai+Aj( ) 。
分析与总结：
这一题是典型的迭代加深搜索+减枝的题目。
迭代加深的搜索（IDS，Iterative Deepening Search）：
迭代加深搜索，实质上就是限定下界的深度优先搜索。即首先允许深度优先搜索K层搜索树，若没有发现可行解，再将K+1后重复以上步骤搜索，直到搜索到可行解。
在迭代加深搜索的算法中，连续的深度优先搜索被引入，每一个深度约束逐次加1，，直到搜索到目标为止。
迭代加深搜索算法就是仿广度优先搜索的深度优先搜索。既能满足深度优先搜索的线性存储要求，又能保证发现一个最小深度的目标结点。
从实际应用来看，迭代加深搜索的效果比较好，并不比广度优先搜索慢很多，但是空间复杂度却与深度优先搜索相同，比广度优先搜索小很多。
对于这一题，首先可以求出最少需要几个元素可以达到n。按照贪心的策略，对于每个元素的值，都选择让它等于一个数的两倍，即对于每个Ai = Ai-1 + Ai-1,当Ai>=n时就跳出循环，得到最少元素个数。
然后从最少步数开始迭代加深搜索。 然后再用上一些减枝技巧即可。
别人失去了信心，他却下决心实现自己的目标。
