您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 實作考拉茲猜想：遞迴與迭代驗證 3n+1 問題

編輯：Java 相關知識

考拉茲猜想簡介

考拉茲猜想又稱 3n+1 猜想、冰雹猜想：對任意正整數 n，重複執行：

n 為偶數 → n = n / 2
n 為奇數 → n = 3n + 1

猜想：最終必定會到達 1，隨後進入 4→2→1 循環。至今未被證明或反證，已驗證至 2^68 以上仍成立。

遞迴實作（教學展示）

package al;

public class CollatzConjecture {
    private int step = 1;

    public static void main(String[] args) {
        long n = 9999999; // 測試較大數值
        System.out.println("初始值：" + n);
        new CollatzConjecture().collatzRecursive(n);
    }

    /** 遞迴版：直觀但大數值可能 StackOverflow */
    private void collatzRecursive(long n) {
        System.out.printf("第 %d 步：%d%n", step++, n);
        if (n > 1) {
            if (n % 2 == 0) {
                collatzRecursive(n / 2);
            } else {
                collatzRecursive(3 * n + 1);
            }
        }
    }
}

迭代實作（生產安全）

public class CollatzIterative {
    /** 迭代版：無堆疊風險，可處理極大數值（配合 BigInteger） */
    public static void collatz(long n) {
        int step = 1;
        System.out.printf("第 %d 步：%d%n", step++, n);
        while (n > 1) {
            if (n % 2 == 0) {
                n = n / 2;
            } else {
                n = 3 * n + 1;
            }
            System.out.printf("第 %d 步：%d%n", step++, n);
        }
    }

    /** BigInteger 版：支援任意大整數 */
    public static void collatzBig(java.math.BigInteger n) {
        int step = 1;
        System.out.printf("第 %d 步：%s%n", step++, n);
        while (n.compareTo(java.math.BigInteger.ONE) > 0) {
            if (n.testBit(0)) { // 奇數
                n = n.multiply(java.math.BigInteger.valueOf(3)).add(java.math.BigInteger.ONE);
            } else { // 偶數
                n = n.shiftRight(1); // 除以 2
            }
            System.out.printf("第 %d 步：%s%n", step++, n);
        }
    }

    public static void main(String[] args) {
        System.out.println("=== long 版 ===");
        collatz(27); // 經典測試案例：111 步，峰值 9232

        System.out.println("\n=== BigInteger 版 ===");
        collatzBig(new java.math.BigInteger("27"));
    }
}

經典測試案例：n = 27

步數：111 步
最大值：9232（遠超初始值）
序列：27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

視覺化與統計分析

public class CollatzStats {
    /** 統計指定範圍內所有數的步數與峰值分佈 */
    public static void analyzeRange(int maxN) {
        int maxSteps = 0, maxPeak = 0;
        int maxStepsN = 0, maxPeakN = 0;

        for (int n = 1; n <= maxN; n++) {
            int steps = 0;
            long peak = n;
            long cur = n;
            while (cur > 1) {
                cur = (cur % 2 == 0) ? cur / 2 : 3 * cur + 1;
                if (cur > peak) peak = cur;
                steps++;
            }
            if (steps > maxSteps) { maxSteps = steps; maxStepsN = n; }
            if (peak > maxPeak) { maxPeak = (int)peak; maxPeakN = n; }
        }
        System.out.printf("1~%d: 最大步數 %d (n=%d), 最大峰值 %d (n=%d)%n", 
            maxN, maxSteps, maxStepsN, maxPeak, maxPeakN);
    }

    public static void main(String[] args) {
        analyzeRange(10000);
        // 輸出範例：1~10000: 最大步數 261 (n=6171), 最大峰值 27114424 (n=7767)
    }
}