約瑟夫環問題（圍圈報數）C 語言數組模擬隊列求解

問題描述

N 人圍成一圈（編號 1~N），從 1 開始報數，報到 M 的人出列，下一人繼續從 1 報數，求最後剩下的人的原始編號。N ≤ 100, M ≤ 9。

數組模擬循環隊列思路

• 用 int a[100] 存儲當前圈中人的編號，0 表示已出列。
• 變量 k 計數報數，cnt 統計出列人數。
• 外層循環直到 cnt == N-1，內層遍歷數組跳過 0，遇到非 0 計數，k==M 時置 0、重置 k、cnt++。
• 利用模運算實現「圈」的效果：索引到達末尾自動回到 0。

完整代碼

#include <stdio.h>

int main() {
    int n, m, a[100] = {0};
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) a[i] = i + 1;

    int cnt = 0, k = 0, i = 0;
    while (cnt < n - 1) {
        if (a[i] != 0) {
            k++;
            if (k == m) {
                a[i] = 0;
                k = 0;
                cnt++;
            }
        }
        i = (i + 1) % n; // 關鍵：循環索引
    }
    for (int i = 0; i < n; i++)
        if (a[i] != 0) { printf("%d", a[i]); break; }
    return 0;
}

關鍵點提煉

1. 循環索引：i = (i+1)%n 替代雙層 for + 手動重置，邏輯更清晰。
2. 原地標記：用 0 標記出列，避免數組移動開銷。
3. 終止條件：剩 1 人即 cnt == n-1。

數學解法補充（O(N)）

遞推公式：f(1)=0; f(i)=(f(i-1)+M)%i，最終答案 f(N)+1。適合大數據範圍（N up to 10^7）。