HDU 3782 卡拉茲猜想（3n+1 問題）步數統計

題目大意

對正整數 n 重複操作：偶數除 2，奇數乘 3 加 1 再除 2（即 (3n+1)/2），直到變為 1。統計操作步數。多測試用例，n=0 結束。

代碼實現

#include <iostream>
using namespace std;

int main()
{
    int n;
    while (cin >> n && n) {
        int count = 0;
        while (n != 1) {
            if (n % 2 == 0)
                n /= 2;
            else
                n = (3 * n + 1) / 2;
            ++count;
        }
        cout << count << endl;
    }
    return 0;
}

關鍵點

• 合併步驟：奇數時 3n+1 必為偶數，題目定義直接除 2 合為一步，避免中間值溢出（但 n 可能暫時超過 32 位，建議用 long long）。
• 循環終止條件：n != 1，猜想未證但驗證範圍內皆收斂。
• 輸入結束：while(cin>>n && n) 兼容 EOF 與 n=0。

優化建議

1. 使用 long long 防溢出（n 最大可能達 10⁹ 級，中間值可達 64 位）。
2. 緩存已計算步數（備忘錄/動態規劃），多測試用例複用。
3. 位運算優化：n & 1 判斷奇偶，n >>= 1 除 2。

優化版片段

long long n;
while (cin >> n && n) {
    int cnt = 0;
    while (n != 1) {
        if ((n & 1) == 0) n >>= 1;
        else n = (3 * n + 1) >> 1;
        ++cnt;
    }
    cout << cnt << endl;
}