【深基5.例3】冰雹猜想

解题思路

按奇偶规则模拟，将每次得到的数连同初值都存入数组，达到 1 后逆序输出。

正确性说明

每步与题目递推规则相同，数组顺序为完整变化过程；逆序遍历得到从 1 到初值的顺序。

易错点

初值与最后的 1 都要输出；用 long long 保存中间值。

复杂度

过程长度 k，时间 O(k)，空间 O(k)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin >> n;
    vector<long long> a;
    while (true) {
        a.push_back(n);
        if (n == 1)
            break;
        if (n % 2)
            n = n * 3 + 1;
        else
            n /= 2;
    }
    for (int i = int(a.size()) - 1; i >= 0; i--) {
        if (i != int(a.size()) - 1)
            cout << " ";
        cout << a[i];
    }
    cout << "\n";
    return 0;
}