C語言經典算法：約瑟夫環問題完整解析與代碼實現

問題描述

有30個同學圍成一個圈，從1開始報數，報到3的同學退出圓圈，請問最後剩下的是哪個同學？並輸出所有出圈同學的順序。這是經典的約瑟夫環問題，也是C語言學習中常見的算法練習。

算法思路

使用數組模擬圓圈，通過標記已退出的同學（設置為0），利用計數器實現報數邏輯。當計數器達到指定數字（此處為3）時，將對應位置標記為0，並重置計數器，繼續下一輪報數，直到只剩下一位同學。

完整代碼實現

int main(void)
{
    // 圍圈報數
    int a[100] = {0};
    int m, n, t = 0;
    int i, j, k = 0;
    scanf("%d%d", &m, &n);
    for (i = 1; i <= m; i++) {
        a[i-1] = i;
    }
    // 每人附上序號
    while (t < m - 1) {
        for (j = 0; j < m; j++) {
            if (a[j] != 0) {
                k++;
                if (k == n) {
                    a[j] = 0;
                    t++;
                    k = 0;
                }
            }
        }
    }
    for (i = 0; i < m; i++) {
        if (a[i] != 0) {
            printf("%d\n", a[i]);
        }
    }
    return 0;
}

代碼解析

• 初始化階段：讀取總人數m和報數上限n，將數組a[0..m-1]初始化為1到m，代表每個同學的編號。
• 模擬報數：外層while循環控制退出人數，內層for循環遍歷數組。遇到非0元素（未退出同學）時計數器k遞增，當k等於n時將該位置置0，表示該同學退出。
• 結果輸出：遍歷數組，輸出未被置0的元素，即為最後剩下的同學編號。

優化建議

該算法時間複雜度為O(m×n)，對於小規模數據完全足夠。若需處理大規模數據，可考慮使用鏈表或數學遞推公式優化至O(m)或O(log m)。