經典約瑟夫環問題：10 個小朋友報數出圈，C 語言高效實現與數學解法

問題描述

10 個小朋友圍成一圈，編號 1~10。從 1 開始報數，報到 3 的小朋友退出圈外，剩下的繼續報數，循環直至剩下最後一位。求最後剩下的小朋友編號。

數學建模：約瑟夫環遞推公式

設 f(n, m) 為 n 人、報數 m 時的獲勝者編號（0-index）。遞推關係：

f(1, m) = 0
f(n, m) = (f(n-1, m) + m) % n

最終答案為 f(n, m) + 1（轉為 1-index）。

C 語言實現：O(n) 時間、O(1) 空間

#include <stdio.h>

int josephus(int n, int k) {
    int res = 0; // f(1, k) = 0
    for (int i = 2; i <= n; i++) {
        res = (res + k) % i;
    }
    return res + 1; // 轉 1-based
}

int main() {
    int n = 10, k = 3;
    printf("最後剩下的小朋友編號：%d\n", josephus(n, k));
    return 0;
}

輸出： 最後剩下的小朋友編號：4

模擬法實現（鏈表/陣列）適合教學演示

// 陣列模擬循環隊列
int simulate(int n, int k) {
    int a[100] = {0}; // 0=在圈內, 1=出局
    int cnt = 0, idx = 0, step = 0;
    while (cnt < n - 1) {
        if (a[idx] == 0) step++;
        if (step == k) {
            a[idx] = 1;
            cnt++;
            step = 0;
        }
        idx = (idx + 1) % n;
    }
    for (int i = 0; i < n; i++)
        if (a[i] == 0) return i + 1;
    return -1;
}

進階擴展：大數據量下的優化

• 當 n 極大（如 10^7）且 k 較小時，可用 遞推公式分段跳躍 優化至 O(k log n)。
• 若需輸出完整出局順序，模擬法不可避免 O(n) 空間，可用 線段樹 或 樹狀數組 實現 O(n log n) 查找第 k 個存活者。

面試加分點

1. 能寫出遞推公式並證明正確性。
2. 能分析模擬法與數學法的時空複雜度優劣。
3. 能處理 k=1、n=1 等邊界情況。
4. 能延伸至「輸出完整出局序列」或「多輪遊戲」變種。

結語： 約瑟夫環是經典環狀結構問題，數學解法極其優雅高效，是面試中展示「從模擬到數學建模」抽象能力的絕佳切入點。