HDU 1032 The 3n+1 Problem：Collatz 猜想循環長度

問題描述

對於正整數 n，定義序列：n 為偶則 n/2，奇則 3n+1，直到變為 1。序列長度（含 1）稱為循環長度。給定區間 [i, j]，求區間內最大循環長度。i,j < 1,000,000。

解題思路

直接模擬計算每個數的循環長度，利用備忘錄（緩存）避免重複計算。由於中間值可能超過 1,000,000，緩存大小可設為較大值（如 5e6）或用 unordered_map。對每組輸入，遍歷區間取最大值。注意 i 可能大於 j，需交換。

代碼實現 (C++)

#include 
using namespace std;
const int MAXC = 5000000;
int cache[MAXC];

int cycleLen(long long n) {
    if (n < MAXC && cache[n]) return cache[n];
    int len = 1;
    if (n != 1) {
        if (n % 2) len += cycleLen(3*n + 1);
        else len += cycleLen(n / 2);
    }
    if (n < MAXC) cache[n] = len;
    return len;
}

int main() {
    cache[1] = 1;
    long long i, j;
    while (cin >> i >> j) {
        long long a = min(i,j), b = max(i,j);
        int maxLen = 0;
        for (long long x = a; x <= b; ++x)
            maxLen = max(maxLen, cycleLen(x));
        cout << i << " " << j << " " << maxLen << endl;
    }
    return 0;
}

複雜度分析

• 時間複雜度：緩存後每個數計算一次，總操作數約數百萬。
• 空間複雜度：O(MAXC)。

總結

Collatz 猜想驗證問題，遞歸 + 備忘錄是標準解法。注意長整型防溢出（3n+1 可能暫時超過 32 位）。