HDU 1601 3n+1 數鏈問題（Collatz 猜想）解題報告

問題描述

給定區間 [i, j] (0 < i ≤ j < 10000)，對區間內每個正整數 n 執行 3n+1 算法：

1. 輸出 n
2. 若 n=1 結束
3. 若 n 為奇數，n = 3n+1；否則 n = n/2
4. 回到第 1 步

定義「鏈長」為序列中數字的個數（含起始值和最終的 1）。求區間內所有整數的最大鏈長。

範例

輸入 1 10，輸出 20（對應 n=9 的序列長度為 20）。

遞歸解法與優化

基本遞歸函數：

int getLinkLen(int n) {
    if (n == 1) return 1;
    return (n & 1) ? getLinkLen(n * 3 + 1) + 1 : getLinkLen(n / 2) + 1;
}

但直接遞歸會重複計算，且 n*3+1 可能超過 32 位整數範圍（雖然題目保證 j < 10000，中間值仍可能溢出 int）。

記憶化優化版

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000000  // 緩存上限，足夠覆蓋中間值

int cache[MAX_N];

int chain_length(long long n) {
    if (n == 1) return 1;
    if (n < MAX_N && cache[n]) return cache[n];
    
    int len = 1 + chain_length((n & 1) ? n * 3 + 1 : n / 2);
    
    if (n < MAX_N) cache[n] = len;
    return len;
}

int main(void) {
    int i, j;
    while (scanf("%d %d", &i, &j) == 2) {
        int max_len = 0;
        for (int n = i; n <= j; n++) {
            int len = chain_length(n);
            if (len > max_len) max_len = len;
        }
        printf("%d\n", max_len);
    }
    return 0;
}

關鍵點總結

• 使用 long long 防止中間計算溢出
• 記憶化（緩存）大幅減少重複計算，時間複雜度接近線性
• 緩存數組大小設為 1,000,000 足以覆蓋題目範圍內的所有中間值
• 輸入處理用 while (scanf("%d %d", &i, &j) == 2) 支持多組測試數據（雖題目說只有一組，但多組更通用）

3n+1 問題是著名的 Collatz 猜想，雖然未證明對所有正整數成立，但計算機已驗證極大範圍。此題考察遞歸、記憶化、整數溢出處理等綜合能力。