解题思路

这道题要求构造一个最短的加法链，使得序列最终能通过逐步相加得到目标数 n。由于 n 的范围较小（1 ≤ n ≤ 100），我们可以采用 DFS + 剪枝 + 迭代加深 的方法来高效求解。

关键步骤

1. 迭代加深（IDDFS）：

   • 逐步增加搜索深度 max_depth，直到找到可行解。
   • 由于要求最短链，IDDFS 可以确保在最小的深度找到解。

2. DFS 搜索：

   • 从 a[0] = 1 开始，每一步尝试所有可能的 a[i] + a[j] 组合来扩展序列。
   • 保证序列严格递增，且不超过目标 n。

3. 剪枝优化：

   • 可行性剪枝：如果当前最大数 a[k] * (2^(max_depth - k)) < n，说明即使后续每一步都翻倍也无法达到 n，直接剪枝。
   • 去重剪枝：避免重复计算相同的数，例如 a[i] + a[j] 和 a[j] + a[i] 只需计算一次。

C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

vector<int> chain;       // 当前加法链
vector<int> result;       // 存储最优解
bool found = false;       // 是否找到解

// DFS + 剪枝 + 迭代加深
void dfs(int depth, int max_depth, int n) {
    if (found) return;    // 已找到解，直接返回

    if (depth == max_depth) {
        if (chain.back() == n) {  // 找到解
            result = chain;
            found = true;
        }
        return;
    }

    // 尝试所有可能的 a[i] + a[j]
    for (int i = chain.size() - 1; i >= 0; --i) {
        for (int j = i; j >= 0; --j) {
            int next = chain[i] + chain[j];
            if (next <= chain.back()) continue;  // 保证严格递增
            if (next > n) continue;             // 不能超过目标数

            // 可行性剪枝：如果后续即使翻倍也无法达到 n，剪枝
            if ((next << (max_depth - depth - 1)) < n) continue;

            chain.push_back(next);
            dfs(depth + 1, max_depth, n);
            chain.pop_back();

            if (found) return;  // 找到解后提前终止
        }
    }
}

int main() {
    int n;
    while (cin >> n && n != 0) {
        found = false;
        chain.clear();
        chain.push_back(1);  // 初始 a[0] = 1

        // 迭代加深，逐步增加 max_depth
        for (int max_depth = 0; ; ++max_depth) {
            dfs(0, max_depth, n);
            if (found) break;
        }

        // 输出结果
        for (size_t i = 0; i < result.size(); ++i) {
            cout << result[i] << " ";
        }
        cout << endl;
    }
    return 0;
}