洛谷P5727《深基5.例3 冰雹猜想》算法竞赛里最经典的入门题之一。题面一句话就能说清给出一个正整数nn≤100按“奇数乘3加1偶数除以2”的规则一直变换直到得到1输出整个变化过程。这道题不像后面的线段树、动态规划那样需要高深理论但它在“深基5”的位置恰好卡住了一批刚学完数组、还没建立起“用结构存中间结果”思维的新手。我见过不少人在评论区问“数组开多大”“最后要不要多输出空格”“为什么我写成n/2就错”其实都在这道题可以一次搞明白。这篇文章会把题目拆开讲透先确认题意和冰雹猜想的背景再对比“边算边输出”和“用数组记录过程”两种思路然后给出C、Python、Java三份可直接提交的代码最后把数组越界、空格格式、死循环这类新手高频问题整理成速查表。无论你是刚开始刷洛谷还是想帮别人讲题都可以参考。1. 题目到底在问什么1.1 冰雹猜想的变换规则与样例说明冰雹猜想的规则非常简洁随便给一个正整数n如果它是偶数下一步就除以2如果它是奇数下一步就乘3再加1。不断重复这个操作最终都会得到一个固定的数——1。用一个最小的非平凡例子跑一遍假设输入3。3是奇数所以先做3 * 3 1 1010是偶数除以2得到55又是奇数乘3加1得到16之后16变88变44变22变1。完整序列就是3 10 5 16 8 4 2 1题目要求输出的就是这一整串数字从输入的n开始一直到1结束中间一个都不能少。它并不要求你说明“为什么一定到1”也不要求你求出步数只要把过程模拟出来再输出。再举一个更长的例子如果输入27过程会非常曲折序列长度会超过一百个数中间最大值甚至能到9232。洛谷题目描述里给了完整的27号序列这也是很多题解喜欢拿来对拍的数据。新手第一次看到这个序列往往会觉得“这哪里是冰雹简直是过山车”。没错这也是“冰雹猜想”这个名字的由来——数字在变化过程中忽大忽小像冰雹在云层里上下翻滚最后落到地面。1.2 这道题真正想考你的能力“深基5.例3”这个编号出自《深入浅出程序设计竞赛基础篇》这本书的第五章那一章的主题是数组。所以这道题虽然用“一边算一边输出”也能做但出题人把它放在这里真正的意图是让你练习“把中间结果存进数组”。具体来说考察三点能不能把一个规则明确、循环往复的过程写成 while 循环能不能用数组或向量把过程中产生的每个数都保留下来能不能按题目要求的格式不多不少地把结果输出。这三点是后续很多模拟题、序列题、动态规划初始化的公共基础。比如“逆序输出变化序列”“输出过程中的最大值”“统计某个数出现过几次”这类变式如果一开始只写成“边算边丢”那就得推倒重写。而用数组存下来之后后面这些需求都只是换个遍历方式的事。2. 两种实现思路与选型拆解2.1 边算边输出代码最简但只有一条路第一种写法很直观不额外开数组循环到哪就输出到哪。C 可以这样写#include iostream using namespace std; int main() { int n; cin n; while (true) { cout n; if (n 1) break; cout ; if (n % 2 1) n 3 * n 1; else n / 2; } cout endl; return 0; }这段代码在洛谷上其实也能通过。它的优点是短几乎不需要解释缺点也很明显所有中间数都只是“路过”没有留下来。如果题目接下来问“倒数第二个数是什么”或者“这个序列里最大的数是多少”你就只能重新模拟一遍。从教学角度来说我不建议新手只用这种写法。因为它会让你误以为“模拟规则”本身就是全部而忽略了“保存中间状态”这个更通用的能力。2.2 数组记录中间过程为变式题留好后路第二种写法是先把每一步结果存进数组最后统一输出#include iostream using namespace std; int main() { int n; cin n; int a[1005]; int cnt 0; a[cnt] n; while (n ! 1) { if (n % 2 1) n 3 * n 1; else n / 2; a[cnt] n; } for (int i 0; i cnt; i) { if (i 0) cout ; cout a[i]; } cout endl; return 0; }核心逻辑是先把初始值 n 存进数组然后每完成一次变换就把新值追加到数组末尾。等到循环结束数组里就是一条完整的冰雹序列数组长度 cnt 就是序列项数。输出时按顺序打印即可。这种做法的优势在于数组一旦建立你拥有的是“整条序列”而不是“流动的数字”。比如想求最大值遍历一次数组想逆序输出倒着遍历一次数组想知道从第几步开始进入某个区间直接按下标访问。作为“深基5”的例题这种把过程保存下来的意识价值远远超过AC本身。2.3 数组开多大、用不用long long新手最容易纠结的问题就是“数组到底开多大”。这题的 n 虽然不超过100但序列长度和数值大小是两回事。以27为例整个冰雹序列有111项也就是说数组至少要有111个位置。如果只开int a[105]跑到一半就越界了。为什么开 1005 这种“看起来有富余”的大小有两个原因在 n ≤ 100 的范围内没有哪个数的冰雹序列会超过几百项1005 绰绰有余算法竞赛中“数组多开一点”是常见习惯只要不 MLE就尽量开够。如果你担心极端数据也可以用 C STL 的vectorint a;每产生一个数就用a.push_back(n);追加完全不用预判长度。对于这道题两种方式都行但vector更稳也更能体现“动态保存”的思路。另一个常见问题是数据类型。n 初始值虽然不超过100但中间值可能变大。27 的中间值最大到9232这当然没超过 int 范围但如果题目把 n 放宽到几万甚至更大3 * n 1就有可能让 int 溢出。因此很多选手习惯直接用long long存 n代价几乎为零却能避免一类隐蔽错误。我的建议是新手阶段直接写long long n;顺手一点。3. 完整代码与关键细节3.1 C 可提交版与逐段解释下面这份是完整可提交的 C 代码我加了注释适合直接照着打一遍#include iostream using namespace std; int main() { long long n; cin n; long long a[1005]; int cnt 0; // 先把初始数字存进去 a[cnt] n; // 只要还没到1就继续变换 while (n ! 1) { if (n % 2 1) { n n * 3 1; } else { n n / 2; } a[cnt] n; } // 按顺序输出两个数之间用一个空格隔开 for (int i 0; i cnt; i) { if (i 0) cout ; cout a[i]; } cout endl; return 0; }分段来看输入部分long long n是为了防止中间值溢出数组a和计数器cnt配合使用a[cnt] n表示“把当前 n 存入数组同时计数器加1”非常常用while (n ! 1)是循环终止条件只要 n 还没变成1就一直变换奇数分支写n * 3 1偶数分支写n / 2顺序不能反输出部分用if (i 0) cout ;避免行末多余空格。3.2 循环条件和奇偶判断最容易踩的坑我见过不少人在循环条件上犹豫到底写while (n ! 1)还是while (n 1)在这道题里两者等价因为正整数经过规则变换不会变成0或负数所以“不等于1”和“大于1”是同一件事。但如果输入数据不规范出现 n0则n ! 1会陷入死循环n 1反而能直接跳过。对题目本身来说无所谓不过养成“用n 1表示正数序列未结束”的习惯也没坏处。奇偶判断也有一个隐蔽坑有人写n % 2 -1这是为了兼容负数。本题输入是正整数写n % 2 1就行。还有人喜欢写(n 1) 1这是用位运算判断奇数效率上几乎没差别但能少写一点字符比赛时很常见。更关键的是更新顺序。每次迭代只能应用一次规则所以必须先根据当前 n 的奇偶性计算新值再把它赋值给 n。如果把n / 2写在奇数判断前面那么奇数也会先被除以2结果完全错。另外如果你用了long long注意输出时cout会自动正确处理不存在%lld的问题。C 的cout在这点上比printf省心。3.3 Python、Java 的写法差异Python 版本非常短但要注意整除符号n int(input()) seq [n] while n ! 1: if n % 2 1: n n * 3 1 else: n n // 2 seq.append(n) print( .join(map(str, seq)))这里最容易犯的错是偶数分支写成n n / 2。Python 中/得到的是浮点数一旦 n 变成小数后续的% 2和* 3 1都会变得很奇怪最终输出一堆带小数点的数。所以必须写成//整除。Java 版本可以用ArrayList充当动态数组import java.util.Scanner; import java.util.ArrayList; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); long n sc.nextLong(); ArrayListLong seq new ArrayList(); seq.add(n); while (n ! 1) { if (n % 2 1) { n n * 3 1; } else { n n / 2; } seq.add(n); } for (int i 0; i seq.size(); i) { if (i 0) System.out.print( ); System.out.print(seq.get(i)); } System.out.println(); } }Java 的ArrayListLong相当于 C 的vectorlong long好处是不用提前指定长度。seq.add(n)一直把新值追加到末尾最后遍历输出。整体逻辑和 C 数组版完全一致。4. 常见问题与调试实录4.1 报错与异常现象速查表现象可能原因解决办法输出结尾多一个空格每个数后面都跟了空格用if (i 0) cout ;先输出空格再输出数本地能跑洛谷显示 RE数组开小了越界访问改用vector或把a[105]换成a[1005]程序半天不结束循环条件写成n ! 1但 n 变成了负数或0检查奇偶分支是否写反用n 1更稳结果对不上样例一开始的 n 没存入数组或者漏存了最后一步确认a[cnt] n;在循环前执行了一次Python 输出带小数偶数分支用了/改成//整除怀疑 int 溢出中间数超过 21 亿n 用long long存储4.2 我常用的本地验证方法拿到这种题我一般不会直接提交。先在本地把样例跑一遍确认输出和题目一致。以输入3为例输出应该是3 10 5 16 8 4 2 1。如果一致再拿题目描述中给出的27长序列做对拍——这是这道题最有效的验证手段因为序列足够长任何一处计算错误都会暴露出来。我还会顺手在代码里加一个“统计序列长度”的调试变量打印cnt的值。比如27的序列应该是111项如果你得到的不是111那说明中间某一步写错了。提交前记得把调试输出删掉或者用cerr输出而不是cout这样在线评测系统不会读到。另外我调试时喜欢把“中间值”也打印出来观察。比如加上这样一句cerr step: n endl;放在 while 循环里就能看到每一步的变换过程。比如 n3 时cerr会输出 10、5、16、8、4、2再加上最后跳出循环时的 n1。这种做法对排查“为什么某一步不对”非常有用也是我向新手推荐的习惯。5. 从冰雹猜想延伸出去5.1 为什么这个简单猜想至今没有证明冰雹猜想的表述简单到小学生都能听懂但至今没有数学家给出严格证明。它在民间也叫“3n1问题”“角谷猜想”。人们已经用计算机验证了非常大范围内的数都能最终落到1但“所有正整数都成立”这一点仍然悬而未决。为什么编程题可以做数学却这么难因为编程本质上是“模拟验证”你只能验证有限个数而数学证明要覆盖无限多个正整数。这个问题的困难在于它介于“可计算”和“不可证明”之间规则极其简单却看不出通用的结构。这也是它适合当编程入门题的原因不需要证明只需要让计算机替你跑一遍。了解这层背景对写代码没有直接影响但能让你明白你在写的不是一个复杂的算法而是在复现一个数学实验。对初学者来说这种“用一个简单循环模拟一个有趣规则”的感觉恰恰是培养编程兴趣的好起点。5.2 换个问法还能怎么考同样的规则把输出要求改一改就能变成新题要求输出序列中最大的数要求输出序列的逆序要求统计从 n 到 1 一共经历了多少步要求找出 n 在某个范围内时哪个数的序列最长。这些变式有个共同点都需要先完整生成序列。如果用“边算边输出”的写法遇到“先求最大再输出”这类问题就得多写一遍逻辑如果用数组存下来最大值就是一次循环遍历的事逆序就是一个for (int i cnt - 1; i 0; i--)。所以我在前面反复强调数组存中间结果不是因为它看起来更“高级”而是因为它在后续场景里真的能复用。如果你把思路再往外扩一步会发现“按规则生成状态用数组保存状态最后统一处理状态”正是很多动态规划题的雏形。洛谷的动态规划题单里很多题目也是“每一步的值由上一步决定然后存进数组或者表格”。所以从这道题切入往 DP 方向过渡是很自然的一条路。5.3 这题在刷题路线中的位置对刚接触算法竞赛的初学者来说P5727 的位置很微妙。它不需要学任何数据结构只要会 if、while、数组就能做但它又很能检验基本功。我见过有人数组版写了半小时问题出在“忘记把初始值存进数组”也见过有人为了省事写边算边输出后来做变式题又回来补课。如果你在按“深基”顺序刷题到这一题时正式进入数组章节后面会有更多“把过程记录下来再处理”的题目。建议是一题吃透比往前赶进度重要。可以先用数组版提交再改写边算边输出版最后想一想“如果题目要求逆序输出我该怎么改”。这三步做完基本上就不会再栽在这类题上。我自己刷这道题的时候一开始也偏爱“边算边输出”觉得数组多此一举。直到后来遇到一道要求输出完整序列的逆序的变式才发现早知道先把中间过程存下来就不会手忙脚乱。所以如果你现在正处于“刚学数组”的阶段请老老实实把数组版写一遍。这个小习惯会让你在后面的刷题路上少踩好几次坑。