1.最直接 但每次都要重算 太慢  

TLE(1s)

#include<iostream>
using namespace std;
int main(){
    int a;
    while(cin >> a){
        long long t=0;
        while(a!=1){
            if(a%2==0)a/=2;
            else a=3*a+1;
            t++;
        }
    cout << t << endl;
    }
}

在此基礎上 把程式加上ios::sync_with_stdio(0); cin.tie(0); 再把endl改成" \n" 就可以AC了(0.6s ,364KB)

如果再把 cin cout 改成 scanf printf 可以到(0.5s, 84KB)

2. DP(動態規劃)

簡單來說就是把已經算過的數字存下來 下一次就不用重複運算

ex:  6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

       8     7      6      5      4      3     2      1     0

這樣下次如果算到6 就把步數直接+=8  算到3就+=7 算到10就+=6 ......

本來以為3n+1數列是收斂的 所以陣列大小我只設了10^6而已

記憶體會爆

#include <iostream>
#include <vector>
using namespace std;

vector<long long> dp(1000001,-1); // 儲存已計算過的結果

long long ans(long long n) {
    if (n == 1) return 0;
    if (dp[n]!=-1) return dp[n];
    if (n % 2 == 0) return dp[n] = 1 + ans(n / 2);
    else return dp[n] = 1 + ans(3 * n + 1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a;
    while (cin >> a) {
        cout << ans(a) << "\n";
    }
}

結果後來發現有時數字會變超級大 (最大到約30億) 如果都用陣列存會爆掉

所以陣列大小不變，但改成如果>10^6就用第一種的方式算，反之DP

AC(0.4s, 4.2MB)

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

vector<int> dp(1'000'001, -1);

long long total(long long a) {
    if (a == 1) return 0;
    if (a <= 1'000'000 && dp[a] != -1) return dp[a];

    long long ans;
    if (a % 2 == 0) {
        ans = 1 + total(a / 2);
    } else {
        ans = 1 + total(3 * a + 1);
    }

    if (a <= 1'000'000) dp[a] = ans;
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a;
    while (cin >> a) {
        cout << total(a) << "\n";
    }
}

如果改成printf scanf -> AC(0.3s, 4.1MB)