解题思路

角谷猜想：任给一个自然数，偶数除以 2，奇数乘 3 加 1，反复运算，最后一定会得到 1。题目要求统计运算了多少次。

思路很简单：

1. 读入 n，用一个计数器 sum 记录运算次数
2. 只要 n 还不是 1，就一直循环：
   • 如果 n 是偶数，n 除以 2
   • 如果 n 是奇数，n 乘 3 加 1
   • 每运算一次，计数器加 1
3. 当 n 变成 1 时循环结束，输出计数器

举个例子：输入 22

• 22 偶数 → 11，1 次
• 11 奇数 → 34，2 次
• 34 偶数 → 17，3 次
• ……继续算下去，最后 2 偶数 → 1
• 总共 15 次

为什么用 while(n!=1)？ 因为要一直运算到 n 变成 1 才停，不知道要循环多少次，用 while 最合适。

参考代码

#include <iostream>
using namespace std;

int main() {
    int n, sum = 0;
    cin >> n;

    // 一直运算，直到 n 变成 1
    while (n != 1) {
        if (n % 2 == 0) {
            // 偶数：除以 2
            n = n / 2;
        } else {
            // 奇数：乘 3 加 1
            n = n * 3 + 1;
        }
        sum++;  // 每运算一次，计数加 1
    }

    cout << sum << endl;
    return 0;
}

复杂度分析

• 时间复杂度：取决于运算次数，一般几十次内就能到 1
• 空间复杂度：O(1)