《算法竞赛进阶指南》加成序列

加成序列

满足如下条件的序列X（序列中元素被标号为1、2、3…m）被称为“加成序列”：

1、X[1]=1

2、X[m]=n

3、X[1]<X[2]<…<X[m-1]<X[m]

4、对于每个 k（2≤k≤m）都存在两个整数 i 和 j （1≤i,j≤k−1，i 和 j 可相等），使得X[k]=X[i]+X[j]。

你的任务是：给定一个整数n，找出符合上述条件的长度m最小的“加成序列”。

如果有多个满足要求的答案，只需要找出任意一个可行解。

输入格式 输入包含多组测试用例。

每组测试用例占据一行，包含一个整数n。

当输入为单行的0时，表示输入结束。

输出格式 对于每个测试用例，输出一个满足需求的整数序列，数字之间用空格隔开。

每个输出占一行。

数据范围 1≤n≤100 输入样例： 5 7 12 15 77 0 输出样例： 1 2 4 5 1 2 4 6 7 1 2 4 8 12 1 2 4 5 10 15 1 2 4 8 9 17 34 68 77

本题应用的是dfs算法里的迭代加深的思想，我们知道dfs搜索的过程是遍历树的一个过程，通常来说我们是一个分支一个分支遍历到底，这样进行搜索的，而迭代加深的思想是我们在搜索之前我们能够基本确定我们的搜索结果在深度较浅的层，我们就可以在每次搜索之前确定搜索的深度，来进行遍历，这样在找到答案之后，就可以直接输出了。

#include <iostream> #include <algorithm> using namespace std; const int N=110; int n; int path[N];//用于存储结果 bool dfs(int u,int k) {//u为当前的迭代深度，k为目标深度 if(u==k)return path[u-1]==n; //由于我们的数组path下标是从0开始的，所以当u==k时 //我们的数组只存储到了u-1的下标 bool st[N]={0};//本次搜索我们做标记那些数已经选过了 //能够去重 for(int i=u-1;i>=0;i--) {//我们在dfs搜索时，要进行从大到小的遍历 //这样能使得总的长度尽量的小（因为两个数相加的大的话，就能更快的接近目标值） for(int j=i;j>=0;j--) {//我们通过两层循环遍历出所有的两个数的和 int s=path[i]+path[j]; if(s>n||s<=path[u-1]||st[N])continue; //这里我们可以剪枝, //(1)当我们两个数相加大于我们所求的数值时，我们直接进行下层循环，因为随着循环的进行，两个数的和是减小的 //(2)我们要明白当前我们得到的和如果符合要求的话我们是要存储到path数组中的因此我们要保持单调递增 //(3)另外我们把每次的合法遍历的结果都做标记，这起到去重的作用 st[s]=true; path[u]=s; if(dfs(u+1,k))return true; } } return false; } int main() { path[0]=1;//结果始终从1开始 while(cin>>n,n) { int k=1;//定义每次迭代加深搜索的深度 while(!dfs(1,k))k++;//每次从1~k不行的话我们就加深搜索的深度 for(int i=0;i<k;i++) cout<<path[i]<<' '; cout<<endl; } return 0; }