P128这道题，圈内通常叫“冰雹数”，我最早是在洛谷上刷到的，题目本身不复杂，但它背后牵出来的考拉兹猜想（Collatz conjecture）能聊的东西特别多。单看题名，很多人以为就是个模拟题，照着递推公式跑一遍就行，但实际写过之后你会发现，这里面既有数学背景、又有程序性能的取舍，还有不少坑——比如int溢出、数组越界、暴力超时。这篇文章我不光把P128的实现讲透，还会把冰雹数为什么难、峰值为什么会经常超出直觉、以及怎么在竞赛环境下写出又快又稳的代码，一并拆开说清楚，适合刚接触算法题或者对3n+1问题感兴趣的朋友参考。
1. 冰雹数到底在算什么：从一个简单规则说起
1.1 一条规则，一段上下翻滚的数列
冰雹数的规则说起来只有两条：给定一个正整数 n，如果 n 是偶数，就除以 2；如果 n 是奇数，就乘以 3 再加 1。得到新的数之后重复这个过程，直到最终变成 1 为止。
举几个具体例子：
- 从 6 出发：6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1，共经过 8 次变换。
- 从 11 出发：11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1，共 14 次。
你会发现这个序列很奇怪，它不像斐波那契数列那样单调增长，也不是简单递减，而是忽上忽下。11 先涨到 34，再掉到 17，接着涨到 52，又降到 26……像冰雹在云层里被气流反复托起又落下，所以就得了“冰雹数”这么个名字。学术上更多人叫它 3n+1 问题，或者考拉兹猜想（Collatz conjecture）。
这个猜想真正让人着迷的是那个“最终变成 1”的结论。至今为止，人类用计算机验证了极其庞大的范围，每个数最终都掉进了 4 → 2 → 1 → 4 这个循环里，但目前仍然没有谁能从数学上严格证明“所有正整数都成立”。这就成了一个著名的未解猜想。作为普通程序员，我们当然没法证猜想，但可以把给定范围内每个数的冰雹序列完整跑出来，输出其中的最大峰值，这正是 P128 的出题方向。
1.2 P128 题目的典型问法
P128 源自洛谷题库，核心考点很简单：
输入一个正整数 n，要求输出 1 到 n 的所有正整数在进行冰雹数变换的过程中，曾经出现过的最大值（包含起始数和 1 之间的所有中间数值）。
举个例子，n 取 3 的时候：
- 1 的序列：1，最大值为 1；
- 2 的序列：2 → 1，最大值为 2；
- 3 的序列：3 → 10 → 5 → 16 → 8 → 4 → 2 → 1，最大值为 16。
所以输出就是 16。这个 16 明显超过 n 本身，而且超出去很多，这也是题目的精髓——如果你直接从 n 出发算一次最大峰值，那就错了，因为你漏掉了前面那些数可能产生更疯狂峰值的情况。
另外还有一类变体是问“在 1 到 n 范围内，哪个数产生的序列最长”，或者“哪个数的峰值最大”并输出这个数。不同的 OJ 对输出要求略有区别，做题前务必看清原题。但无论哪种问法，核心计算单元都是一样的：给定起点 x，按规则生成序列，记录峰值或长度。只要把这个组件写对了，剩下的就是遍历范围和优化性能。
2. 核心思路拆解：暴力模拟为什么不够，怎么升级成高效算法
2.1 先想清楚一件事：要不要真的把整个序列存下来
初学时最容易犯的毛病是把序列存进 vector 或 list，然后遍历求最大值。这个习惯在题目数据范围较小时没有隐患，比如 n 只有 100，那怎么折腾都行。但真实 OJ 测试点往往会覆盖到上万、上百万的 n，甚至更多，这时候有两个问题会冒出来：
- 存储开销大。每个数平均需要的变换步数不是固定的，有的数很小，几步就到 1；有的数比如 27，需要 111 步才能到 1，中间最高能冲到 9232，跨度很大。如果你把所有数的完整序列都存下来，内存占用会立刻失控。
- 重复计算严重。不同的起始数在演变过程中会经过大量相同的“中间数”，比如从 5 出发会经过 16、8、4、2、1，而从 10 出发同样会经过 5、16、8、4、2、1。如果每次都从头算一遍，那 16、8、4、2、1 这些尾部路径就被白白重复了很多次。
所以 P128 这类题的正确姿势，是从头到尾都只用“迭代变量”来跟踪当前值，而不是把所有历史数值装进容器。峰值用一个 long long 变量实时记录即可，序列本身没必要完整保存。
2.2 记忆化搜索：把已经算过的结果变成复用资产
解决重复计算最直接的办法是记忆化（memoization）。核心思想：开一个数组 dp，dp[i] 表示从数字 i 出发到 1 的某个关键指标，比如“过程中最大峰值”或“序列总步数”。计算一个新的数 x 时，每走到一个已经算过的中间数 y，就直接利用 dp[y] 的结果，不用再一路算到 1。
以“峰值”为例，伪代码可以这样写：
function calcPeak(x, dp): if x 已经被计算过: return dp[x] 和对应的起始数 // 否则一路模拟，并记录过程中的最大峰值 current = x maxPeak = x while current != 1: if current 是偶数: current = current / 2 else: current = current * 3 + 1 maxPeak = max(maxPeak, current) if current 已经被计算过: // 这里发生命中的时候，不用继续往下走 maxPeak = max(maxPeak, 已知的从 current 出发的最大峰值) break dp[x] = maxPeak return maxPeak这段逻辑看着简单，但有个关键点：当 current 命中某个已经算过的数 y 时，后面的 4 → 2 → 1 阶段全部可以剪枝。极端情况下，如果整个范围内所有数都计算完之后，后半段的峰值查询相当于 O(1) 查表，整体速度提升非常明显。
2.3 时间复杂度和空间复杂度的取舍
- 暴力模拟：假设 1 到 n 每个数平均需要 L 步到达 1，复杂度就是 O(n × L)。L 并没有严格上界，但对于普通范围内的整数，平均大概几十步到一百多步。n 到了一千万甚至更高，暴力基本必挂。
- 记忆化搜索：每个数在首次被计算之后，后续再被引用时都是 O(1)。整体上每个数字最多被真正模拟一次，时间复杂度约等于 O(n × 平均首次路径长度)，但因为大量中间数被共享，实际运算量远低于暴力。空间上需要 O(n) 的 dp 数组，可以通过 vector 或 unordered_map 来实现。
听起来记忆化没代价，实际倒也不是。如果题目给出的 n 特别大，比如 10^7 量级以上，开一个能覆盖到多少下标就成问题。冰雹序列的中途值往往会超过 n，甚至远超 n，所以数组大小不能只开到 n，还得预留一部分。聪明的做法是先用 unordered_map 做缓存，等把数值压缩到一定范围内再查数组；或者干脆把数组开到 n 的 4 到 8 倍，覆盖大部分中间值。经验上，一个数在达到小于起始值的点之前，可能先膨胀到起始值的数倍，这个倍数我没有严格数学证明，但竞赛实践里 4 到 8 倍通常够用，超过的部分落到 unordered_map 兜底。
2.4 为什么有些优化是伪优化，别被误导
网上有不少讨论 3n+1 问题的加速技巧，比如“只有奇数才需要乘 3 加 1，偶数直接右移”，这类当然没问题。但有些奇技淫巧，比如根据 n 的奇偶性直接跳步预测峰值，看起来很聪明，实际在题目环境里并不一定可靠。
我自己的建议是：优先保证代码逻辑直观、可调试，再考虑黑魔法。竞赛里最重要的不是脑洞，而是在限定时间内把正确的答案稳定跑出来。一个写清楚的记忆化版本，完全能应对绝大多数 P128 的测试点。
3. 实操过程：从读完题到 AC 的完整代码实现
3.1 环境准备和数据范围确认
写代码前，先确认三件事：
- 题目给的 n 上限是多少。这决定了数组开多大、用 int 还是 long long。
- 输出要求是“峰值最大是多少”，还是“峰值最大的那个起始数是多少”。不同要求前缀代码完全不一样。
- 时间限制是多少。如果给的很宽，暴力也能过；如果只有几十毫秒，那记忆化基本是必选项。
P128 原题我印象里 n 并不会给到特别夸张，但为了保险，我一律按高范围处理，全程使用 long long，原因稍后说明。
3.2 C++ 版实现（推荐竞赛用）
我先把直接可交的代码贴出来，再逐段讲为什么这么写。
#include <bits/stdc++.h> using namespace std; const int MAXN = 1000005; vector<long long> peak(MAXN * 8, -1); // 峰值缓存，初始为 -1 表示未计算 long long dfs(long long x, long long originMax) { // 如果 x 已经在缓存范围内且已计算，直接返回缓存值 if (x < (long long)peak.size() && peak[x] != -1) { return peak[x]; } long long current = x; long long maxVal = x; while (current != 1) { if (current % 2 == 0) { current /= 2; } else { current = current * 3 + 1; } maxVal = max(maxVal, current); // 命中缓存：后续路径不用再走 if (current < (long long)peak.size() && peak[current] != -1) { maxVal = max(maxVal, peak[current]); break; } } if (x < (long long)peak.size()) { peak[x] = maxVal; } return maxVal; } int main() { ios::sync_with_stdio(false); cin.tie(0); long long n; cin >> n; long long ans = 0; for (long long i = 1; i <= n; i++) { ans = max(ans, dfs(i, 0)); } cout << ans << "\n"; return 0; }这段代码的核心是 dfs 函数。它接收一个起始数 x，返回从 x 出发的序列里“最大峰值”。注意参数里那个 originMax 其实没有用到，我在写的时候习惯性留一个扩展位，方便以后改造成“返回序列长度”之类的变体，你也可以删掉。
while 循环内部每次先处理 current 的奇偶性，然后更新 maxVal，再检查能否命中缓存。为什么要“先更新再检查”？因为 current 本身也可能是峰值，比如 3 变换到 10 这一步，10 就是当前序列的峰值，必须先比一比。
另一个关键是缓存超界处理：冰雹序列的中间值可能远远超过 n，甚至超过 MAXN * 8，这时候不能直接访问 peak[current]，会导致数组越界。我用了一个判断current < peak.size()把超界的部分排除掉，让它继续往下走。当然如果后续又回到一个比较小的数字，依然能命中缓存。
3.3 Python 版实现（适合调试和小数据）
如果你只是自己练手，或者用 Python 交题，逻辑一样，只是需要注意递归深度问题。我一般不用递归写，而是用迭代 + 字典缓存：
import sys sys.setrecursionlimit(1 << 25) def ice_peak(x, memo): if x in memo: return memo[x] original = x current = x max_val = x while current != 1: if current % 2 == 0: current //= 2 else: current = current * 3 + 1 max_val = max(max_val, current) if current in memo: max_val = max(max_val, memo[current]) break memo[original] = max_val return max_val def main(): n = int(input().strip()) memo = {1: 1} ans = 0 for i in range(1, n + 1): ans = max(ans, ice_peak(i, memo)) print(ans) if __name__ == "__main__": main()Python 版最爽的地方是不用关心数组上限，因为 memo 是字典，无限扩展。但代价是字典查找比数组慢，n 特别大的时候可能 TLE。所以我平时的做法是：先用 C++ 写正式提交版，用 Python 做小范围对拍和结果验证，两边结果一致再交 C++。
3.4 关于 long long 和 int 的踩坑提醒
这是 P128 最容易翻车的地方之一。3n+1 过程里，当前值如果是奇数，下一步会变成 3 倍再加 1。一个 32 位 int 能存的最大值是 2147483647，如果你传入一个接近这个值的奇数，乘 3 再加 1 就会整数溢出，变成负数，然后 while 循环卡在 current 永远不等于 1，直接死循环或者返回一个错误结果。
举例说明：假如某个中间数是 715827883，它乘以 3 加 1 等于 2147483650，已经超过了 int 上限，在 C++ 里会溢出成 -2147483646。负数对 2 取余不是常规意义上的偶数判断，程序立刻乱套。所以只要范围稍大，我就无脑用 long long。别觉得“我的 n 很小，中间值能有多大”，27 这个不起眼的数都能把峰值推到 9232，一旦 n 上千万，中间峰值冲到几千万甚至上亿都很正常。long long 在竞赛环境下几乎保证不会溢出，而且现在评测机对 64 位运算支持很好，性能损失几乎可以忽略不计。
3.5 运行结果演示
我在本地用 n = 27 测试过，如果只看 27 这一个数的峰值，序列走势是这样的：
- 27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
从 27 出发，峰值 9232，步数 111 步，最高点是起始数的 341 倍还多。这也说明为什么不能简单预估峰值和原数的比例。但如果你只算到 n = 27，答案并不是 9232，而是 1 到 27 所有数里峰值最大的那个，实测是 9232。很多时候你会发现，峰值最大的起始数往往是区间内比较靠后的某个奇数，具体是谁得算完才知道，这也是这题有趣的地方。
4. 边界情况、运行效率与常见错误排查
4.1 边界值测试：n = 1、2、3 都不能错
写题必测的三个小值：n = 1，答案是 1；n = 2，序列 2 → 1，峰值 2；n = 3，前面算过，峰值 16。这三个数据量极小，人工心算一遍再和程序对比，能快速发现最基础的逻辑问题。
比如有人把初始峰值设成 0，那 n = 1 时循环一次都不进，maxVal 一直等于 1，没事。但如果初始最大值设成 INT_MIN，其他人又用了负数缓存判断，可能就出幺蛾子。我的习惯是 maxVal 初始化为 x 本身，因为序列第一项就是 x，峰值至少是它，这样逻辑上最顺。
4.2 数组开多大？缓存命中率怎么权衡？
上一部分代码里我用了const int MAXN = 1000005; vector<long long> peak(MAXN * 8, -1);，也就是给 n 上限的一百万，数组开到八百万。为什么是 8 倍？这不是标准答案，而是我对很多测试集的妥协。
理论上来讲，冰雹序列中的数字可以涨到多大，没有已知的简单上界。但在实际测试数据中，n 在一百万以内时，绝大多数中间值不会超过 n 的 4~8 倍。开 8 倍空间能覆盖大多数情况，配合数组 O(1) 访问，速度极快。万一某个数的中间值超出数组范围，代码里还有兜底逻辑（current < peak.size()判断），不会越界。
如果你图省事，直接用 unordered_map 做缓存，空间是无限了，但每个数字访问都要哈希，性能明显下降。所以正确的做法是：数组为主、超界回退到“不缓存、继续模拟”，这样可以兼顾速度和正确性。想更稳妥的话，还可以把数组容量开成 n 的 16 倍，内存一般也顶得住。
4.3 常见运行时错误速查表
我把这几年刷题和答疑时遇到的典型问题整理成一张表，方便你对照排查：
| 症状 | 可能原因 | 解决方案 |
|---|---|---|
| 程序死循环 | 使用 int 导致溢出，current 变成负数 | 全局改用 long long |
| 答案比预期小 | 只算了 1 到 n 中某个数而不是所有数 | 确认遍历范围是 1 到 n |
| 答案比预期大 | 把某个极端数的峰值错当成了全局答案 | 仔细检查输出逻辑，是否漏掉 max 比较 |
| 内存超限 | 把每个数的完整序列都存下来 | 不存序列，只存峰值变量 |
| 超时 | 没有使用记忆化 | 添加 dp 缓存，命中后直接跳出 |
| 段错误 | 访问 peak[current] 但 current 远超数组大小 | 增加下标越界判断，或用 unordered_map 兜底 |
4.4 如何验证你的答案
小数据可以手动验证，大数据怎么验证？我的做法是分段对拍。先写一个完全不优化的暴力版（用 Python 或 C++ 都行），让它跑 n = 100、1000、10000，记下结果。再让优化版跑同样的数据，两个结果一致，基本就能确定主逻辑没问题。之后再用优化版跑大 n，看看性能是否可接受。
这个方法不需要什么高级工具，一个终端两个程序就够了。尤其适合 P128 这种结果受输入范围影响很大的题，跑几组边界数据，比你坐在那儿盯半天代码管用得多。
4.5 性能优化进阶：跳过必然不是答案的数
如果题目把 n 上限抬得特别高，比如 10^8 量级，即使记忆化也可能逼近时间极限。这时候可以考虑一些基于观察的剪枝策略。
一个常见的观察是：如果某个起始数 x 是偶数，那么 x 的第一步必然变成 x/2，所以从 x/2 出发得到的序列峰值至少覆盖了从 x 出发到 x/2 之后的所有可能峰值。换句话说，x/2 的峰值会大于等于 x 的峰值？这个说法不能简单成立，因为从 x 出发先变成 x/2，之后路径和 x/2 完全一致，所以峰值确实不会超过 x/2 序列的峰值。这样，所有偶数起始数都没有必要作为候选，只需遍历奇数。这个剪枝能让计算量减小一半，而且不影响答案。
再进一步，有些数据范围下还可以只从 3、7、15 这样的形式入手，但推导复杂且不通用，我不建议在普通题目里用，容易偷鸡不成蚀把米。
5. 从 P128 往外延伸：冰雹数背后的数学魅力和变体题
5.1 为什么叫“冰雹数”？为什么是未解猜想？
我前面说“像冰雹”，其实还可以从另一个角度理解。冰雹在云层里反复上升下降，最后落到地面；这个数列也是，从任意起点出发不断上下震荡，最终全部“落”到 1。整个过程是确定性的，没有任何随机，但结果表现出强烈的混沌感。科学家用计算机验证了非常大的范围，所有数都满足最终到 1 的性质，但就是证明不了“所有数都满足”。这就是数学上“猜想容易、证明极难”的典型范例。
这种看似简单却无法证明的问题，非常适合用来训练程序员的递归、模拟、状态缓存思维。你不需要懂高深的数论，只要会循环和判断就能写出程序，但你会在调试过程中逐步体会到：也许某个很大的数隐藏着一次次超乎预期的暴涨，值得你去优化、去验证、去认真对待每一个边界条件。
5.2 常见变体：不只求峰值，还求步数
P128 求的是峰值，但很多 OJ 上还有求“序列长度”的同类题，比如给定 n，输出 1 到 n 中哪个数对应的冰雹序列最长。实现起来核心函数几乎一样，只是把“更新最大峰值”换成“累加步数”。这里有个小细节：记忆化步数时，如果命中缓存，当前步数要加上缓存里的步数，而不是直接替换。伪代码如下：
long long dfsSteps(long long x) { if (cache[x] != -1) return cache[x]; if (x == 1) return 0; long long steps = 0; long long current = x; while (current != 1) { if (current % 2 == 0) { current /= 2; } else { current = current * 3 + 1; } steps++; if (current < cache.size() && cache[current] != -1) { steps += cache[current]; break; } } cache[x] = steps; return steps; }这种变体在面试题里也很常出现，因为考察的是你有没有真正理解记忆化的语义，而不只是背模板。
5.3 可视化：把冰雹数画出来是什么效果
有段时间我闲着没事，把 1 到 1000 的冰雹序列用折线图画出来过。每个起始数一条线，终点都是 1，但中间起伏完全不同。有的很快就俯冲到底，有的则先冲到数百、再慢慢跌回 1。整个图叠在一起，像一片倒置的山峰群，特别有视觉冲击力。
这也是一个很好的自检方式：如果你跑出来的数据画出来完全不像“上下翻滚”，而是一路飙升不回头，那基本说明代码里把奇偶判断写反了。常见错误是current % 2 == 0时去乘 3 加 1，结果序列越跑越大，死循环直到溢出。画图验证比肉眼盯数字直观多了。
5.4 这题的竞赛价值和个人收获
说实话，P128 的天花板不高，但它的价值在于把“看似简单的数学过程”和“竞赛编程中的优化思维”结合得很好。你没法靠背答案通过测试点变化，必须动态理解每一步的状态转移。同时它还教你一个深刻教训：不要想当然。永远别觉得峰值一定比 n 小、步数一定很少、int 一定够用。我见过太多人在小数据上跑得欢，一到大数据就崩，原因就是忽略了溢出和性能。
6. 最后分享几个我实际摸出来的小经验
先说验证习惯。我每次改动代码之后，都会固定跑一遍 n = 1、3、27、100000 这组测试。n = 1 验证最小边界，n = 3 验证峰值超过 n 的逻辑，n = 27 是经典的大波动样本，n = 100000 用来粗略确认性能。这套组合在我复盘其他冰雹数类题目时也一直在用，几乎能把八成逻辑错误扼杀在提交之前。
再说代码风格。C++ 版本里一定要加ios::sync_with_stdio(false); cin.tie(0);，否则大数据输入输出可能慢到超时。这个细节容易被忽略，尤其是 n 到百万级别后，cin 不加这行和 scanf 完全是两个速度档位。
还有一个小建议：如果做 P128 只是为了学习，建议你先别急着优化，先写一版最朴素的暴力模拟，把每一步结果打印出来，亲眼看 27 的完整序列是怎么翻滚的。然后再加记忆化、加剪枝，对比速度差异。这样你对“优化到底优化了什么”会有非常实在的体感，而不是停留在背代码的层面。学算法题最怕的就是没踩过坑就直接抄答案，那样下次换个马甲你还是认不出来。
