【例35.2】 角谷猜想

解题思路

n不等于1时按奇偶规则更新，并同时打印该步完整等式。达到1后输出End。

正确性说明

按上述推导执行：每次仅处理当前输入或当前步骤，并把它对答案的贡献计入对应状态。所有需要处理的情况均被覆盖，结束时保存的量就是题目所求。

易错点

输入1时没有运算行，只输出End；等式不带空格。

复杂度

变化步数k，时间O(k)，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin >> n;
    while (n != 1) {
        if (n % 2) {
            long long next = n * 3 + 1;
            cout << n << "*3+1=" << next << "\n";
            n = next;
        } else {
            cout << n << "/2=" << n / 2 << "\n";
            n /= 2;
        }
    }
    cout << "End\n";
    return 0;
}