POJ 2484 - 環形取石子遊戲（SG 函數/對稱策略）

問題描述

n 個石子圍成環，兩人輪流取，每次可取 1 個或相鄰 2 個。無法取者負。輸出獲勝者（Alice 先手，Bob 後手）。

博弈論分析

若為一條線（非環），先手取中間 1 或 2 個使左右對稱，然後鏡像策略必勝。但環狀下，先手無法直接對稱。

關鍵觀察：n < 3 時先手直接取完獲勝。n ≥ 3 時，先手無論取什麼，都會破環為線，且留下的線段長度之和 = n-1 或 n-2。後手作為線段遊戲的先手，可採用對稱策略獲勝。因此 n ≥ 3 時先手必敗（Bob 勝）。

代碼實現（C++）

#include 
int main() {
    int n;
    while (scanf("%d", &n) && n) {
        if (n < 3) puts("Alice");
        else puts("Bob");
    }
    return 0;
}

結論

極簡邏輯：n=1,2 Alice 勝；n≥3 Bob 勝。無需複雜 SG 計算。