HDU 1032 The 3n+1 Problem：Collatz 猜想區間最大步數

題目大意

對於區間 [a, b] 內的每個整數 n，定義序列：n 為偶數則 n/2，奇數則 3n+1，直到變為 1。求區間內最大步數（含起始數）。輸入多組 a,b，輸出原順序 a b maxSteps。

解法：預計算 + 區間查詢

因 a,b ≤ 1,000,000（實際測試數據），可預計算 1..1,000,000 每個數的步數，區間查詢取最大值。但題目輸入無明確上限，採用單次計算 + 排序取最大即可。

代碼實現

#include <cstdio>
#include <algorithm>
using namespace std;
int steps[1000010];

void calc_range(int a, int b) {
    int n = 0;
    for (int i = a; i <= b; i++) {
        int t = i, k = 0;
        while (t != 1) {
            if (t % 2 == 0) t /= 2;
            else t = 3 * t + 1;
            k++;
        }
        steps[n++] = k + 1; // 含起始數
    }
    sort(steps, steps + n);
    printf("%d %d %d\n", a, b, steps[n-1]);
}

int main() {
    int a, b;
    while (scanf("%d %d", &a, &b) == 2) {
        if (a > b) swap(a, b);
        calc_range(a, b);
    }
    return 0;
}

優化提示

• 可用 unordered_map 記憶化遞歸/迭代計算步數，避免重複計算（如 8→4→2→1，計算 8 時可直接用 4 的結果）。
• 注意 3n+1 可能溢出 32 位有符號整數，建議用 long long 或 unsigned int。