【深基5.例3】冰雹猜想

题意

给出正整数 n。不断执行：

如果 n 是奇数，变成 3n + 1；
如果 n 是偶数，变成 n / 2。

直到变成 1。要求从最后的 1 开始，倒序输出整个变化序列。

思路

先按题意正向模拟，把每次出现的数字加入列表 sequence。

当 n != 1 时继续循环。每轮根据奇偶选择下一步：

text

1
2奇数：n = n * 3 + 1
偶数：n = n // 2

循环结束后，sequence 中保存的是从初始值到 1 的顺序。题目要求倒序输出，所以反转列表后输出即可。

这题是列表保存过程再倒序输出的练习，不创建 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：用 int(input()) 读取单个整数，用 print(*sequence) 输出列表。
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md：// 是整数除法，适合偶数除以 2。
n % 2 == 1 判断奇数。
sequence.append(n) 保存过程值，sequence.reverse() 原地反转。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12n = int(input())

sequence = [n]
while n != 1:
    if n % 2 == 1:
        n = n * 3 + 1
    else:
        n //= 2
    sequence.append(n)

sequence.reverse()
print(*sequence)

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/**
 * 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-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

int a[10005]; // 保存冰雹序列
int cnt;      // 序列长度

int main() {
    int n;
    cin >> n;
    // 先把起始数存入
    a[++cnt] = n;
    // 按规则模拟，直到变成 1
    while (n != 1) {
        if (n % 2 == 1) // 奇数：3n+1
            n = n * 3 + 1;
        else            // 偶数：n/2
            n /= 2;
        a[++cnt] = n;
    }
    // 题目要求倒序输出（从 1 开始）
    for (int i = cnt; i >= 1; i--) cout << a[i] << " ";
    return 0;
}

Pythonic 写法

用条件表达式写奇偶变换，sequence[::-1] 切片反转输出：

python

1
2
3
4
5
6n = int(input())
sequence = [n]
while n != 1:
    n = n * 3 + 1 if n % 2 else n // 2
    sequence.append(n)
print(*sequence[::-1])

递归写法

这道题还非常适合用来学习递归。观察变化过程：知道了当前数 x，下一步还是执行同一套规则，只是数字变成了 3x+1 或 x/2——"处理当前数"和"处理下一步"是同一个问题，只是规模变了，这正是递归适用的场景。

递归写法最关键的地方是倒序输出的实现：

text

1先递归调用处理下一个数，等它返回后，再输出当前数 x

因为每一层递归都要等"更深层"的递归全部返回才继续，输出动作发生在回溯路上，所以先输出 1，再一层层倒着输出 2、4、8……，天然就是题目要求的倒序，不需要数组保存、也不需要反转。

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/**
 * 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-08-14 11:26
 * update_at: 2026-08-14 11:26
 */
#include <bits/stdc++.h>
using namespace std;

// 递归生成冰雹序列：dfs(x) 表示处理当前数字 x。
// 先递归计算下一步，回溯时再输出 x，
// 这样输出的顺序正好是题目要求的倒序（从 1 开始）。
void dfs(int x) {
    if (x == 1) {          // 到达序列末尾 1，开始回溯输出
        cout << x << " ";
        return;
    }
    if (x % 2 == 1)        // 奇数：下一步是 3x+1
        dfs(x * 3 + 1);
    else                   // 偶数：下一步是 x/2
        dfs(x / 2);
    cout << x << " ";      // 回溯时输出当前数
}

int main() {
    int n;
    cin >> n;
    dfs(n);                // 从初始值开始递归
    return 0;
}

Python 写法：

python

1
2
3
4
5
6
7
8
9
10
11
12
13def hailstone(n):
    if n == 1:
        print(1, end=" ")
        return
    if n % 2 == 1:
        hailstone(n * 3 + 1)
    else:
        hailstone(n // 2)
    print(n, end=" ")


n = int(input())
hailstone(n)

还有一种常见的递归写法，递归只负责按正向顺序把每个数存进全局数组，倒序输出交给后面的循环：

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/**
 * 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-08-14 11:26
 * update_at: 2026-08-14 11:26
 */
#include <bits/stdc++.h>
using namespace std;

int a[10000];
int cnt;
// 递归生成冰雹序列：dfs(x) 表示处理当前数字 x。
// 先递归计算下一步，回溯时再输出 x，
// 这样输出的顺序正好是题目要求的倒序（从 1 开始）。
void dfs(int x) {
    a[++cnt] = x;
    if (x == 1) {          // 到达序列末尾 1，开始回溯输出
        return;
    }
    if (x % 2 == 1)        // 奇数：下一步是 3x+1
        dfs(x * 3 + 1);
    else                   // 偶数：下一步是 x/2
        dfs(x / 2);
}

int main() {
    int n;
    cin >> n;
    dfs(n);                // 从初始值开始递归
    for(int i = cnt; i >= 1 ;--i )
        cout << a[i] << " ";
    return 0;
}

两种递归写法对比：

写法	递推下去时做什么	回溯回来时做什么	输出方式
`main-rec.cpp`	只算下一步	输出当前数	边回溯边输出，不需要数组
`main-rec2.cpp`	把当前数存入数组	什么都不做	回溯结束后，循环倒序输出数组

main-rec2.cpp 的优点是"生成序列"和"输出序列"两件事完全分开：递归只负责按正确顺序产生数据，输出逻辑还是熟悉的循环倒序。它适合需要把序列保存下来继续处理（比如统计、二次遍历）的场景；main-rec.cpp 则展示了递归最经典的"回溯时做事"模式，代码更短，但输出分散在递归返回的路上，不易做进一步处理。两种写法递归深度相同，都是 $O(k)$ 的调用栈。

学习递归要抓住三个要点：

递归出口：x == 1 时不再调用自己，直接输出并返回，这是递归必须有的终止条件；
递归调用：当前数字不是 1 时，把下一步数字作为参数调用自己；
回溯输出：递归调用结束后才输出当前数，输出顺序因此反过来。

本题 $n \leqslant 100$ ，冰雹序列最多只有几十个数，递归深度很小，不用担心栈溢出；Python 默认递归上限是 1000，完全够用。

Guide 风格代码

cppbook《C++ 快速入门》教学风格的递归写法（std:: 前缀、i += 1 循环、0 起始下标）：

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/**
 * 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-08-14 15:21
 * update_at: 2026-08-14 15:21
 */
#include <iostream>

// print_path(x)：处理当前数字 x 的递归函数。
// 先递归计算下一步，回溯时再输出 x，
// 输出顺序正好是题目要求的倒序（从 1 开始）。
void print_path(int x) {
    if (x == 1) {                  // 到达序列末尾 1，开始回溯输出
        std::cout << x << ' ';
        return;
    }
    if (x % 2 == 1) {              // 奇数：下一步是 3x+1
        print_path(x * 3 + 1);
    } else {                       // 偶数：下一步是 x/2
        print_path(x / 2);
    }
    std::cout << x << ' ';         // 回溯时输出当前数
}

int main() {
    int n;
    std::cin >> n;
    print_path(n);                 // 从初始值开始递归
    return 0;
}

复杂度

设序列长度为 k。模拟和反转都是 $O(k)$ ，空间复杂度是 $O(k)$ 。三种递归写法的时间复杂度同样是 $O(k)$ ：main-rec.cpp 用调用栈代替显式数组，main-rec2.cpp 是调用栈加上存序列的数组，空间都是 $O(k)$ 。

总结

这题不要一边倒序一边输出。循环写法：先把正向过程存下来，再反转输出。递归写法：利用调用栈天然保存了路径，在回溯时输出即可得到倒序——同一个倒序问题，两种思路殊途同归，也顺便体会了"递归时机器用栈帮你记住了每一层"。