LeetCode 292：Nim Game（尼姆遊戲）

一、題目描述

你和朋友玩 Nim 遊戲：一堆石子，每人輪流取 1~3 顆，取走最後一顆者勝。你先手。雙方都極其聰明。給定石子數 n，判斷你能否贏。

範例： n=4 → 你必輸（無論取幾顆，朋友都能取走最後一顆）。

二、規律分析

列出小 n 的勝負態：

n=1: 勝 (取1)
n=2: 勝 (取2)
n=3: 勝 (取3)
n=4: 負 (對手必勝)
n=5: 勝 (取1, 剩4給對手)
n=6: 勝 (取2)
n=7: 勝 (取3)
n=8: 負
...

發現規律：n % 4 == 0 時先手必輸，否則先手必勝。
證理：若 n=4k，先手取 x(1~3)，後手取 4-x，保持剩餘為 4 的倍數，最終後手取走最後一顆。

三、代碼實現（C++）

class Solution {
public:
    bool canWinNim(int n) {
        return n % 4 != 0;
    }
};

四、複雜度分析

• 時間複雜度：O(1)
• 空間複雜度：O(1)

本題為經典博弈論入門題，找規律即可秒殺。