C/C++實現約瑟夫環問題：循環隊列解法與常見錯誤分析

約瑟夫環是經典算法題：n人圍圈，從1開始報數，數到k者出列，循環至無人。本文提供基於循環隊列的C語言實現，並深度剖析常見邏輯錯誤。

正確算法思路

1. 初始化隊列，將1~n入隊。
2. 循環執行：出隊計數，計數達k則輸出該元素（出列），否則重新入隊（繼續報數）。
3. 直到隊列為空。

代碼實現（含詳細註釋）

#include <stdio.h>
#define MAX 100

typedef struct {
    int data[MAX];
    int front, rear;
} CirQueue;

void InitQueue(CirQueue *Q) { Q->front = Q->rear = 0; }
int IsEmpty(CirQueue *Q) { return Q->front == Q->rear; }
int IsFull(CirQueue *Q) { return (Q->rear + 1) % MAX == Q->front; }
void EnQueue(CirQueue *Q, int x) {
    if (IsFull(Q)) return;
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MAX;
}
int DeQueue(CirQueue *Q) {
    if (IsEmpty(Q)) return -1;
    int x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX;
    return x;
}

void Josephus(int n, int k) {
    CirQueue Q; InitQueue(&Q);
    for (int i = 1; i <= n; i++) EnQueue(&Q, i);

    int count = 0;
    while (!IsEmpty(&Q)) {
        int person = DeQueue(&Q);
        count++;
        if (count == k) {
            printf("%d ", person); // 出列
            count = 0;
        } else {
            EnQueue(&Q, person); // 繼續報數
        }
    }
}

int main() {
    Josephus(10, 3); // 測試樣例
    return 0;
}

原代碼四大致命錯誤

1. 未初始化隊列：front/rear未歸零，導致判空/判滿邏輯失效。
2. 隊列操作邏輯顛倒：入隊/出隊條件與數據流向錯誤，未形成真正循環。
3. 循環終止條件錯誤：`while((S.rear+1)!=S.front)`在未初始化時無意義，初始化後永真導致死循環。
4. 算法核心邏輯缺失：未實現「報數k出列、否則重入隊」的核心流程，僅做簡單入隊輸出。

進階優化方向

• 使用數學遞推公式O(k log n)解法（適合極大n）。
• 鏈表模擬實現O(nk)但更直觀。
• STL `list` + 迭代器實現更簡潔的C++版本。

掌握約瑟夫環不僅是刷題，更能鍛煉循環數據結構邏輯與邊界條件處理能力。