PAT 乙級 1001 (3n+1)猜想：Collatz 序列步數計算

問題描述

對任意自然數n：偶數→n/2；奇數→(3n+1)/2。重複直到n=1，求步數。n≤1000。

直接模擬

#include 
int main() {
    int n, step = 0;
    scanf("%d", &n);
    while (n != 1) {
        if (n % 2 == 0) n /= 2;
        else n = (3 * n + 1) / 2;
        step++;
    }
    printf("%d\n", step);
    return 0;
}

樣例追蹤

n=3：3→5→8→4→2→1，共5步。

擴展思考

• 對於大n可用備忘錄（動態規劃）緩存中間結果加速。
• 猜想未證，但經驗上所有n < 2^68均收斂。
• 步數增長不規則，n=27需111步達到峰值9232。