P4367 角谷猜想（基础）

解题思路

角谷猜想说的是：随便给一个正整数，如果它是奇数，就乘 3 再加 1；如果它是偶数，就除以 2。反复这样处理，最后一定会变成 1。这个猜想至今没人能证明，但我们可以用程序来"验证"，也就是把整个过程一步步输出出来。

算法非常直白，用一个 while 循环模拟： 第一步，先输出当前的数 n； 第二步，判断 n 是奇数还是偶数，奇数就 n = n × 3 + 1，偶数就 n = n ÷ 2； 第三步，重复以上两步，直到 n 变成 1，最后再输出一个 1。

拿样例 n = 5 来走一遍：5 是奇数，变成 16；16 是偶数，变成 8；8 → 4；4 → 2；2 → 1。输出的就是 5 16 8 4 2 1，和样例一致。

边界情况：n 最小可以是 1，这时循环一次都不用执行，直接输出 1 就行，因为 while 的条件 n != 1 一开始就不成立。还有一个容易踩的坑：处理过程中数字可能会变大，比如 n = 27 时中间会出现 9232 这样的大数，所以要用 long long 来存，不能只开 int。

参考代码

// 程序用途：验证角谷猜想，输出正整数n经过处理变成1的过程
#include <iostream>
using namespace std;

int main() {
    long long n;                      // 中间的数可能变大，用long long保险
    cin >> n;
    while (n != 1) {                  // 只要还没变成1就继续处理
        cout << n << " ";             // 先输出当前的数
        if (n % 2 == 1) n = n * 3 + 1;   // 奇数：乘3再加1
        else n = n / 2;               // 偶数：除以2
    }
    cout << 1 << endl;                // 最后再输出1
    return 0;
}

复杂度分析

角谷过程通常很快就能收敛到 1，循环次数和 log n 差不多，最多也就几百步；空间上只用了几个变量，额外空间复杂度是 O(1)。