ZeroJudge 解題筆記：c039. 00100 - The 3n + 1 problem

作者：王一哲
日期：2026年2月5日


ZeroJudge 題目連結：c039. 00100 - The 3n + 1 problem

解題想法

用一個自訂函式 cycle 處理數值 n 的循環次數，寫起來會比較方便。函式內部按照題目的要求，分別處理 n 為奇數、偶數兩種狀況，更新 n 的數值。

Python 程式碼

使用時間約為 2.3 s，記憶體約為 3.3 MB，通過測試。

import sys

def cycle(n):
    times = 1  # 如果 n 等於 1，至少有 1 次
    while n != 1:
        times += 1
        if n%2 == 1: n = 3*n + 1
        else: n //= 2
    return times

for line in sys.stdin:
    a, b = map(int, line.split())
    print(f"{a:d} {b:d} ", end="")
    if a > b: a, b = b, a
    imax = 0
    for i in range(a, b+1):
        imax = max(imax, cycle(i))
    print(f"{imax:d}")

C++ 程式碼

使用時間約為 17 ms，記憶體約為 92 kB，通過測試。

#include <cstdio>

int cycle(int n) {
    int times = 1;  // 如果 n 等於 1，至少有 1 次
    while(n != 1) {
        times++;
        if (n%2 == 1) n = 3*n + 1;
        else n /= 2;
    }
    return times;
}

int main() {
    int a, b;
    while(scanf("%d %d", &a, &b) != EOF) {
        printf("%d %d ", a, b);
        if (a > b) {
            int c = a;
            a = b;
            b = c;
        }
        int imax = 0;
        for(int i=a; i<=b; i++) {
            int tmp = cycle(i);
            if (tmp > imax) imax = tmp;
        }
        printf("%d\n", imax);
    }
    return 0;
}