易–中 · 循环模拟
冰雹序列
偶数就砍一半,奇数就乘三加一。没人证明得了「是不是所有数最终都会到 1」—— 但你的循环能替你验算任何一个数。
一句话答案n 是偶数就除以 2、是奇数就变成 3n + 1，一直数到 n 等于 1 —— n = 1 本身要输出 0 步，这是最容易被忘掉的情况。
题目
输入: 一个整数 n(1 ≤ n ≤ 100000)。
输出: 到达 1 需要多少步。如果 n 本来就是 1,输出 0。
样例:
| 输入 | 输出 |
|---|---|
6 | 8 |
1 | 0 |
以 6 为例:6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1。数箭头 —— 一共 8 个。到达 1 是终点,它本身不算一步。
你的解答
「运行我的输入」用的自定义输入
判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。
卡住了？提示
提示 1 — 规则是循环体,不是公式
这没有闭式解 —— 你算不出答案,只能走一遍。这就是 while 循环:不断变换 n,每变换一次计一步。
提示 2 — 奇偶各一个分支
n % 2 == 0 表示偶数 → n = n / 2。否则 → n = 3 * n + 1。这里整数除法正是你要的:既然已经确认是偶数,就不必担心余数。
提示 3 — 差一错误藏在循环条件里
用 while (n != 1),在循环体内自增。如果你把 steps 初始化成 1,或者在输出之后才自增,每个答案都会差一 —— 而且 n = 1 会输出 1 而不是 0。
题解（先自己试试！）
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int steps = 0;
while (n != 1) {
if (n % 2 == 0) n = n / 2;
else n = 3 * n + 1;
steps++;
}
cout << steps << endl;
return 0;
}这就是考拉兹猜想:从任何正整数出发,序列似乎总会到 1,但没人证明得了。你的程序是一次小小的数学实验 —— 试试 27,看它先爬到 9232 再一路落下。这种「把规则跑一遍,然后看数字」的习惯,正是面对没有公式的问题时建立直觉的方式。继续:数单词。
深度解析
为什么这样做对
这条规则没有公式,所以你算不出答案,只能一步步走。把规则写成循环体、把步数写成计数器 —— 这是所有模拟类问题的通用骨架。
代价
O(步数),而且没人能给出通用的上界 —— 这正是考拉兹猜想至今未解的原因。n ≤ 100000 时实测都在几百步以内。
常见错法
- 把
steps初始化成 1,或者在输出之后才自增,每个答案都差一 —— 而且n = 1会输出 1 而不是 0。 - 把
n != 1写成n > 1:正数下看着等价,可一旦某次笔误让序列掉进负数,循环就再也停不下来了。
下一步
下一步,把「边扫边记状态」用到文本上:数单词。
记住这两句
- 没有公式的规则,就写成循环体,让机器替你走。
- 到达终点不算一步 —— 循环条件和计数器必须对齐。
🐞 这段是错的 —— 点开,亲手让它挂一次
steps 从 1 开始 —— 每个答案都多一
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int steps = 1;
while (n != 1) {
if (n % 2 == 0) n = n / 2;
else n = 3 * n + 1;
steps++;
}
cout << steps << endl;
return 0;
}