P128这道题圈内通常叫“冰雹数”我最早是在洛谷上刷到的题目本身不复杂但它背后牵出来的考拉兹猜想Collatz conjecture能聊的东西特别多。单看题名很多人以为就是个模拟题照着递推公式跑一遍就行但实际写过之后你会发现这里面既有数学背景、又有程序性能的取舍还有不少坑——比如int溢出、数组越界、暴力超时。这篇文章我不光把P128的实现讲透还会把冰雹数为什么难、峰值为什么会经常超出直觉、以及怎么在竞赛环境下写出又快又稳的代码一并拆开说清楚适合刚接触算法题或者对3n1问题感兴趣的朋友参考。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……像冰雹在云层里被气流反复托起又落下所以就得了“冰雹数”这么个名字。学术上更多人叫它 3n1 问题或者考拉兹猜想Collatz conjecture。这个猜想真正让人着迷的是那个“最终变成 1”的结论。至今为止人类用计算机验证了极其庞大的范围每个数最终都掉进了 4 → 2 → 1 → 4 这个循环里但目前仍然没有谁能从数学上严格证明“所有正整数都成立”。这就成了一个著名的未解猜想。作为普通程序员我们当然没法证猜想但可以把给定范围内每个数的冰雹序列完整跑出来输出其中的最大峰值这正是 P128 的出题方向。1.2 P128 题目的典型问法P128 源自洛谷题库核心考点很简单输入一个正整数 n要求输出 1 到 n 的所有正整数在进行冰雹数变换的过程中曾经出现过的最大值包含起始数和 1 之间的所有中间数值。举个例子n 取 3 的时候1 的序列1最大值为 12 的序列2 → 1最大值为 23 的序列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。核心思想开一个数组 dpdp[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 为什么有些优化是伪优化别被误导网上有不少讨论 3n1 问题的加速技巧比如“只有奇数才需要乘 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; vectorlong 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 最容易翻车的地方之一。3n1 过程里当前值如果是奇数下一步会变成 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答案是 1n 2序列 2 → 1峰值 2n 3前面算过峰值 16。这三个数据量极小人工心算一遍再和程序对比能快速发现最基础的逻辑问题。比如有人把初始峰值设成 0那 n 1 时循环一次都不进maxVal 一直等于 1没事。但如果初始最大值设成 INT_MIN其他人又用了负数缓存判断可能就出幺蛾子。我的习惯是 maxVal 初始化为 x 本身因为序列第一项就是 x峰值至少是它这样逻辑上最顺。4.2 数组开多大缓存命中率怎么权衡上一部分代码里我用了const int MAXN 1000005; vectorlong 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 的完整序列是怎么翻滚的。然后再加记忆化、加剪枝对比速度差异。这样你对“优化到底优化了什么”会有非常实在的体感而不是停留在背代码的层面。学算法题最怕的就是没踩过坑就直接抄答案那样下次换个马甲你还是认不出来。
