Java 約瑟夫環問題：報數 3 出列

經典約瑟夫環（Josephus Problem）

n 人圍圈，從 1 開始報數，報到 3 的人出列，求最後剩下的人的原始編號。

原始碼問題分析

提供的程式碼中 if (t == 4) 應為 t == 3，且輸出邏輯 (i+1)%4 錯誤。以下提供正確實作。

布林陣列模擬法（修正版）

import java.util.Scanner;

public class JosephusSimulation {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("請輸入總人數 n：");
        int n = sc.nextInt();

        boolean[] alive = new boolean[n];
        Arrays.fill(alive, true);
        int remaining = n;
        int count = 0;
        int idx = 0;

        while (remaining > 1) {
            if (alive[idx]) {
                count++;
                if (count == 3) {
                    alive[idx] = false;
                    remaining--;
                    count = 0;
                }
            }
            idx = (idx + 1) % n; // 環狀移動
        }

        // 找出倖存者
        for (int i = 0; i < n; i++) {
            if (alive[i]) {
                System.out.println("倖存者原始編號：" + (i + 1));
                break;
            }
        }
    }
}

數學遞推公式法（O(n) 時間 O(1) 空間）

設 f(n, k) 為 n 人報數 k 的倖存者索引（0-based）。遞推關係：

f(1, k) = 0

f(n, k) = (f(n-1, k) + k) % n

public class JosephusMath {
    public static int josephus(int n, int k) {
        int result = 0; // f(1,k)=0
        for (int i = 2; i <= n; i++) {
            result = (result + k) % i;
        }
        return result + 1; // 轉 1-based 編號
    }

    public static void main(String[] args) {
        System.out.println("n=10, k=3 倖存者：" + josephus(10, 3)); // 輸出 4
    }
}

測試對照表

進階：Queue 模擬（教學用）

Queue q = new LinkedList<>();
for (int i=1; i<=n; i++) q.offer(i);
while (q.size() > 1) {
    q.offer(q.poll()); // 1
    q.offer(q.poll()); // 2
    q.poll();          // 3 出列
}
System.out.println(q.peek());

直觀易懂，但空間 O(n)。