解题思路

给自然数 n 的左边加一个不超过 n 一半的数，加完后还能继续加，问一共能产生多少个新数。

思路：递归。

设 he(n) 处理自然数 n，统计从 n 出发能产生多少个新数（不含 n 本身）。

对 n：

1. 可以添加 1 到 n÷2 之间的任意一个数 i
2. 每添加一个 i，就产生一个新数（计数加 1）
3. 添加完 i 后，还能继续给 i 的左边加数，所以递归调用 he(i)
4. n 是 1 时，1÷2=0，没有可添加的数，直接返回

举例 n=6：

• 可添加 1、2、3
• 加 1 → 16，再给 1 加不了，共 1 个新数
• 加 2 → 26，还能给 2 加 1 → 126，共 2 个新数
• 加 3 → 36，还能给 3 加 1 → 136，共 2 个新数
• 总共 5 个新数

参考代码

#include <iostream>
using namespace std;

long long s = 0;

void he(int n) {
    if (n == 1) return;  // 1 不能再添加

    for (int i = 1; i <= n / 2; i++) {
        s++;      // 产生一个新数
        he(i);    // 对添加的数继续处理
    }
}

int main() {
    int n;
    cin >> n;
    he(n);
    cout << s;
    return 0;
}

复杂度分析

• 时间复杂度：约 O(N²)，递归处理每个数
• 空间复杂度：O(N)，递归深度