Addition Chains（加法链）

形式化题目

给定正整数 $n$ ，构造一个严格递增的数列 $a_0,a_1,\dots,a_m$ ，满足：

$a_0=1$ ， $a_m=n$ ；
对每个 $k\ (1\leqslant k\leqslant m)$ ，存在 $0\leqslant i,j\leqslant k-1$ （ $i,j$ 可以相等），使 $a_k=a_i+a_j$ 。

要求 $m$ 最小，输出任意一条满足条件的数列。多组数据， $n=0$ 结束。

样例： $n=5$ 时 1 2 4 5 是一条最短链（ $1{+}1=2$ ， $2{+}2=4$ ， $4{+}1=5$ ， $m=3$ ）。

正解

思路

朴素想法：直接从 $[1]$ 开始 DFS，每次从已有数中任取两个（可相等）求和作为下一个数，直到末尾等于 $n$ ，找最短链。问题是链长没有上限，搜索树无限深，而且找到的第一条链不一定最短。

观察一（链长有天然上界）：链严格递增且 $a_1=a_0+a_0=2$ ；每一步末值最多翻倍（ $a_k\leqslant 2a_{k-1}$ ），所以 $a_m\leqslant 2^m$ ，即 $m\geqslant\lceil\log_2 n\rceil$ 。反过来， $n<2^k$ 时用「 $1,2,4,\dots,2^{k-1},n$ 」型构造（每项翻倍，最后 $n=2^{k-1}+(n-2^{k-1})$ ，只需 $n-2^{k-1}$ 在链中）总能给出不超过 $\lceil\log_2 n\rceil+1$ 的链。所以最优链长被夹在 $\lceil\log_2 n\rceil$ 与 $\lceil\log_2 n\rceil+1$ 附近，是一个非常小的数。

观察二（迭代加深恰合口味）：我们要的是最短链，DFS 找到的不一定最短；BFS 又要存整层状态。既然答案深度不超过 $\lceil\log_2 n\rceil+2$ 左右，用迭代加深（IDDFS）：深度上限从 $\lceil\log_2 n\rceil$ 起逐层 +1，第一层找到的解就是最短链。同一个浅层子树会被重复搜索几次，但深度极小，代价可忽略。

观察三（两个方向界剪枝）：当前链末值为 $\textit{last}$ 、还剩 $d$ 步时：

若 $\textit{last}\cdot 2^d<n$ ，后面每步最多翻倍也够不到 $n$ ，剪掉；
反过来，新的候选值 $v$ 之后还剩 $d-1$ 步，若 $v\cdot 2^{d-1}<n$ 同样无望，即 $v\geqslant\lceil n/2^{d-1}\rceil$ 。把候选从大到小枚举，小于该下界的整段尾巴直接 break，而不是逐个 continue。

从大到小枚举还有个贪心作用：优先逼近 $n$ 的候选更可能快速命中，让成功分支极短。

候选生成：下一个数只能是已有链中两数之和（下标可相等）。链长为 $m$ 时候选只有 $O(m^2)$ 个，用集合推导式去重后排序即可。本题数据范围小（经典版本 $n\leqslant 10^4$ ）， $O(m^2)$ 枚举完全够用。

样例 $n=77$ 的搜索过程（IDDFS 深度上限为 8 时命中）：

步骤	链	新值来源
0	1 2 4 8	翻倍逼近（下界剪枝迫使前段尽量大）
5	+9	$8{+}1$
6	+17	$9{+}8$
7	+34	$17{+}17$
8	+68	$34{+}34$ ，此时剩 1 步须出 $77$
9	+77	$68{+}9$ ✔

代码

Python 版：

python

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 22:00
# update_at: 2026-07-05 22:00

import sys
from functools import lru_cache


def min_depth(n: int) -> int:
    """n=1..n*2 的最优链长预计算不了，这里只给出深度下界：每步最多翻倍。"""
    d = 0
    v = 1
    while v < n:
        v *= 2
        d += 1
    return d


def search(chain: list[int], used: set[int], depth: int, n: int) -> list[int] | None:
    """在剩余 depth 步内把链延伸到 n；找到即返回整条链，否则返回 None。"""
    last = chain[-1]
    if last == n:
        return chain
    # 剪枝一：每步最多翻倍，翻 depth 倍也够不到 n
    if last << depth < n:
        return None

    # 候选新值 = 前面的数两两之和（i、j 可相等，含翻倍），从大到小尝试以贪心逼近 n
    m = len(chain)
    cands = sorted({chain[i] + chain[j] for i in range(m) for j in range(i + 1)}, reverse=True)
    lower = max(-(-n >> (depth - 1)), last + 1)         # 須大于 last，且剩 depth-1 步翻倍须够到 n
    for v in cands:
        if v < lower:
            break                                       # cands 从大到小，后面只会更小
        if v > n or v in used:
            continue
        chain.append(v)
        used.add(v)
        res = search(chain, used, depth - 1, n)
        if res is not None:
            return res
        chain.pop()
        used.remove(v)

    return None


def solve_one(n: int) -> list[int]:
    """迭代加深：链长从下界开始逐层加深，第一条找到的链就是最短链。"""
    if n == 1:
        return [1]
    for depth in range(min_depth(n), 23):
        res = search([1], {1}, depth, n)
        if res is not None:
            return res
    raise AssertionError("n 太大，深度上限 22 不够")


def solve() -> None:
    out: list[str] = []
    for token in sys.stdin.buffer.read().split():
        n = int(token)
        if n == 0:
            break
        out.append(' '.join(map(str, solve_one(n))))
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 01:40
 * update_at: 2026-10-05 01:41
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXD = 32;      // 答案链的最大长度；n 在本题范围内远小于 2^30
const int MAXCAND = MAXD * MAXD;

ll n;                     // 当前询问的 n
ll chain[MAXD];           // 迭代加深时正在构造的链，chain[0] = 1，严格递增
ll best[MAXD];            // 搜到的最短链
ll best_len;              // 最短链最后一项的下标，即最优步数 m
ll cand[MAXD][MAXCAND];   // cand[step] 保存该层链里两两相加得到的候选值，按层存放避免递归互相覆盖
int cand_cnt[MAXD];       // cand_cnt[step] 是 cand[step] 里的候选个数

// 返回 n 的步数下界：每步末值最多翻倍，所以至少要 log2(n) 步。
ll depth_lower_bound(ll x)
{
    ll d = 0;
    ll v = 1;
    while (v < x) {
        v *= 2;
        d++;
    }
    return d;
}

// 上取整的 a / b。
ll ceil_div(ll a, ll b)
{
    return (a + b - 1) / b;
}

// dfs(step, remain)：当前链最后一项下标是 step，还剩 remain 步可用。
// 能在 remain 步内走到 n 就保存整条链并返回 true，否则返回 false。
bool dfs(ll step, ll remain)
{
    ll last = chain[step];
    if (last == n) {
        best_len = step;
        for (ll i = 0; i <= step; i++) {
            best[i] = chain[i];
        }
        return true;
    }

    // 剪枝一：末值每步最多翻倍，remain 步后也够不到 n。
    if (last << remain < n) {
        return false;
    }

    // 候选新值只能由链中两数相加得到（下标可相同，即翻倍），收集后从大到小尝试。
    cand_cnt[step] = 0;
    for (ll i = 0; i <= step; i++) {
        for (ll j = 0; j <= i; j++) {
            cand[step][cand_cnt[step]] = chain[i] + chain[j];
            cand_cnt[step]++;
        }
    }
    sort(cand[step], cand[step] + cand_cnt[step], greater<ll>());

    // 剪枝二：新值 v 之后还剩 remain-1 步，必须满足 v * 2^(remain-1) >= n；
    // 同时链严格递增，v 至少要大于 last。
    ll lower = ceil_div(n, 1LL << (remain - 1));
    if (lower < last + 1) {
        lower = last + 1;
    }

    for (int k = 0; k < cand_cnt[step]; k++) {
        ll v = cand[step][k];
        if (v < lower) {
            break;                       // 候选从大到小排列，后面只会更小
        }
        if (v > n) {
            continue;
        }
        if (k > 0 && v == cand[step][k - 1]) {
            continue;                    // 同一候选值只试一次
        }
        chain[step + 1] = v;
        if (dfs(step + 1, remain - 1)) {
            return true;
        }
    }
    return false;
}

int main()
{
    while (scanf("%lld", &n) == 1) {
        if (n == 0) {
            break;
        }

        chain[0] = 1;
        // 迭代加深：从步数下界开始逐层 +1，第一条搜到的链就是最短链。
        for (ll depth = depth_lower_bound(n); depth <= 30; depth++) {
            if (dfs(0, depth)) {
                break;
            }
        }

        for (ll i = 0; i <= best_len; i++) {
            if (i > 0) {
                printf(" ");
            }
            printf("%lld", best[i]);
        }
        printf("\n");
    }
    return 0;
}

复杂度

设最优链长为 $L=\Theta(\log n)$ （夹在 $\lceil\log_2 n\rceil$ 与其 $+2$ 之间）。每个结点生成候选 $O(L^2)$ 个，IDDFS 总代价约为 $O(L^3\cdot 2^{O(L)})$ 的搜索树规模；由于 $L\leqslant 20$ （ $n\leqslant 10^5$ 时 $L\leqslant 21$ ），实际运行毫秒级。空间为递归栈 $O(L)$ 。

总结

「每步最多翻倍」给出链长下界 $\lceil\log_2 n\rceil$ ，把无界搜索变成深度极小的搜索。
求最短 + 深度小 ⇒ 迭代加深是标配：每层第一条找到的链即最短链。
双向界剪枝：末值翻倍够不到 $n$ 剪掉；候选值太小（剩余步数翻倍够不到 $n$ ）整段剪掉。
候选从大到小枚举，让「贪心逼近 + 下界剪掉尾巴」同时生效。

Addition Chains（加法链）

目录

形式化题目

正解

思路

代码

复杂度

总结