题目描述

满足如下条件的序列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

算法：迭代加深 + 剪枝 时间复杂度O(?)

分析题目：样例给出的数据 n=77时才9深度，数据范围n最多到100，目测不会有多少深度，但是每一层的决策很多，也就是度很大，时指数级别的，最终答案没有多少深度，但有的分支可能深度很深。根据闫氏语录：当树满足：有的节点很深但答案在很浅的层里面且度很大，这样的题目用迭代加深做最为合适，来看代码。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 25,M = 110;

int seq[N];

int depth,n;

bool dfs(int u)
{
    if(u > depth) return false;

    if(seq[u - 1] == n) return true;

    bool st[M] = {0}; //把重复的值给剪掉，使得度最多只有100

    for(int i=u-1;i >= 0;i--)
        for(int j = i;j >= 0;j--)
        {
            int sum = seq[i] + seq[j];
            if(sum > n||sum <= seq[u-1] ||st[sum]) continue;//可行性剪枝
            st[sum] = true;
            seq[u] = sum;
            if(dfs(u+1)) return true;
        }
    return false;
}


int main(){

    seq[0] = 1;

    while(cin >> n,n)
    {
        depth = 1;
        while(!dfs(1)) depth ++;
        for(int i=0;i<depth;i++)
            cout << seq[i] << " ";
        puts("");
    }


    return 0;
}