經典算法題：1 到 100 圓圈取數問題，最後剩下哪個數？

題目描述

有 1 到 100 共 100 個數，排成一個圓圈。從 1 開始，每隔 1、2、3、4... 個數取走一個數，循環進行，直到最後剩下一個數為止。具體規則：

• 初始（隔 0 個）取走 1
• 隔 1 個數（跳過 2）取走 3
• 隔 2 個數（跳過 4、5）取走 6
• 隔 3 個數（跳過 7、8、9）取走 10
• 第一輪數到 100 後，從剩餘數字繼續，直到剩最後一個

問題：最後剩下的是哪個數？若擴展到 1 到 n 呢？

解題思路

這是一個變體的约瑟夫斯問題，間隔步長遞增。使用 ArrayList 模擬圓圈，維護當前索引與步長計數器，循環移除元素直到剩最後一個。

Java 實現

public static int selectNumber(int n) {
    int result = -1;
    ArrayList<Integer> nums = new ArrayList<>();
    int index = 0;      // 當前移除索引
    int count = 0;      // 步長計數器（隔幾個數）
    int pIndex = 0;     // 記錄上一次移除索引

    // 初始化 1 到 n
    for (int i = 1; i <= n; i++) {
        nums.add(i);
    }

    while (nums.size() > 1) {
        // 單輪遍歷移除
        while (index < nums.size()) {
            nums.remove(index);
            count++;
            pIndex = index;
            index += count;
        }
        // 計算下一輪起始索引（環狀處理）
        index = count - (nums.size() - pIndex);
        while (index > nums.size() - 1) {
            index = index - nums.size();
        }
    }

    result = nums.get(0);
    return result;
}

public static void main(String[] args) {
    int surviver = selectNumber(100);
    System.out.println("The surviver is: " + surviver);  // 輸出: 31
}

執行結果

程式執行後輸出：The surviver is: 31

即 1 到 100 按規則取數後，最後剩下的數字是 31。

算法複雜度分析

• 時間複雜度：O(n²) — ArrayList remove 操作需位移元素
• 空間複雜度：O(n) — 儲存 n 個整數

對於 n=100 規模，效能完全足夠。若 n 極大，可考慮鏈表或數學推導優化。

擴展思考

此問題展示了模擬法解決變體约瑟夫斯問題的通用思路。關鍵在於正確處理環狀索引計算與動態步長遞增邏輯。讀者可嘗試修改步長規則（如固定步長、斐波那契步長等）觀察結果變化。