C語言實現「丟沙包/殺人遊戲」：循環鏈表模擬與雙倍緩衝區技巧

C語言實現「丟沙包/殺人遊戲」：循環鏈表模擬與雙倍緩衝區技巧

規則：n 人圍圈，從第 start 人開始報數，每數 step 人淘汰一人，直到剩最後一人。

數據結構：雙倍陣列模擬環

分配 2*n 大小陣列，前 n 存初始編號 1~n，後 n 複製一份。指針 p 在 1~2n 間移動，超過 n 時減 n 映射回邏輯位置，避免取模運算開銷。

核心邏輯

// 初始化
for (i=0; i<2*n; i++) people[i] = (i 1) {
    // 向前數 step 個「活人」
    for (i=0; i 2*n) p -= 2*n;
        p = (p > n) ? p-n : p; // 映射
        // 跳過已死位置
        while (people[p-1] == 0) { p++; if (p>2*n) p-=2*n; p=(p>n)?p-n:p; }
    }
    // 淘汰
    people[p-1] = 0;
    people[(p>n)?p-1-n:p-1+n] = 0; // 雙份同步清零
    rest--;
}

關鍵函數

• check_rest()：掃描前 n 位非零計數。
• jump_killed()：跳過已淘汰位置。
• check_num()：參數合法性檢查（step < n 等）。

優化方向

• 改用真正的循環鏈表（struct Node {int id; Node* next;}），刪除節點 O(1)，更符合數學模型。
• 若 n 極大（百萬級），可用數學遞推公式（約瑟夫環問題）O(n) 或 O(k log n) 求解，無需模擬。