約瑟夫問題完整解法：隊列模擬圓圈消除與模數優化技巧

編輯：關於C語言

約瑟夫問題完整解法：隊列模擬圓圈消除與模數優化技巧

問題描述：N 人圍成圓圈，編號 1~N。1 號持刀，每輪傳遞 M 人，持刀者殺死下一人，刀傳給死者下一人。重複至剩 1 人。輸入 T 組測資，輸出各組倖存者編號總和。

核心洞察：隊列模擬圓圈

隊列順序即圓圈順序
「傳遞 M 人」= 隊首出隊、入隊 M 次
「殺死下一人」= 隊首出隊（殺人者），再出隊（被殺者），殺人者入隊

關鍵優化：模數剪枝

當 M 很大時，直接迴圈 M 次會 TLE。觀察：隊列長度為 L 時，傳遞 M 步等價於 M % L 步。


for (int k = 0; k < M % current_size; k++) {
    int x = dequeue();
    enqueue(x);
}

完整演算法流程


for 每組測資 (N, M):
    初始化隊列 1..N
    for i = 1 to N-1:           // 需殺死 N-1 人
        steps = M % size        // 關鍵優化
        repeat steps 次: 移動隊首到隊尾
        killer = dequeue()      // 持刀者
        dequeue()               // 被殺者（丟棄）
        enqueue(killer)         // 持刀者回隊尾
    survivor = queue_front()
    sum += survivor
輸出 sum

C 語言實現（循環隊列）


#include <stdio.h>

int q[1000];
int head, tail, size;

void enqueue(int x) {
    if (size == 0) head = tail = 0;
    else tail = (tail + 1) % 1000;
    q[tail] = x;
    size++;
}

int dequeue() {
    int x = q[head];
    head = (head + 1) % 1000;
    size--;
    return x;
}

int main() {
    int T, N, M, sum = 0;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &M);
        head = tail = size = 0;
        for (int i = 1; i <= N; i++) enqueue(i);
        for (int i = 1; i < N; i++) {
            int steps = M % size;
            for (int k = 0; k < steps; k++) {
                int x = dequeue(); enqueue(x);
            }
            int killer = dequeue();
            dequeue();              // 被殺者
            enqueue(killer);        // 殺人者回圈
        }
        sum += q[head];
    }
    printf("%d\n", sum);
    return 0;
}

範例驗證

輸入：
3
5 2
4 3
8 4

過程 (5,2)：
初始: 1 2 3 4 5
M=2: 移動2步→3 4 5 1 2, 殺4, 刀給5 → 5 1 2 3
M=2: 移動2步→2 3 5 1, 殺3, 刀給5 → 5 1 2
M=2: 移動2步→2 5 1, 殺5, 刀給1 → 1 2
M=2: 移動2步→1 2, 殺2, 刀給1 → 1
倖存: 1

(4,3) 倖存: 2
(8,4) 倖存: 1
總和: 1+2+1=4 → 輸出 4

複雜度分析

時間：O(T * N * (M % N)) → 優化後實測極快
空間：O(N)

常見錯誤與避坑

錯誤	正確	說明
未取模直接迴圈 M 次	steps = M % size	M 可達 1000，N=1000 時無優化會 TLE
殺人邏輯順序錯誤	先移動、再殺下一個、殺人者回隊	題目：傳 M 人→持刀者殺下一個→刀給死者下一個
隊列大小不夠	開 1000+ 或動態配置	N ≤ 1000，開 1005 即可
多組測資未重置隊列	每組重新 init head/tail/size	避免上組殘留資料干擾