Nim 游戲
- Nim 游戲
- 題目描述
- 博弈論
- 上期經典算法
Nim 游戲
難度 - 簡單
原題鏈接 - Nim游戲
題目描述
你和你的朋友,兩個人一起玩 Nim 游戲:
桌子上有一堆石頭。
你們輪流進行自己的回合, 你作為先手 。
每一回合,輪到的人拿掉 1 - 3 塊石頭。
拿掉最后一塊石頭的人就是獲勝者。
假設你們每一步都是最優解。請編寫一個函數,來判斷你是否可以在給定石頭數量為 n 的情況下贏得游戲。如果可以贏,返回 true;否則,返回 false 。
示例 1:
輸入:n = 4
輸出:false
解釋:以下是可能的結果:
- 移除1顆石頭。你的朋友移走了3塊石頭,包括最后一塊。你的朋友贏了。
- 移除2個石子。你的朋友移走2塊石頭,包括最后一塊。你的朋友贏了。
3.你移走3顆石子。你的朋友移走了最后一塊石頭。你的朋友贏了。
在所有結果中,你的朋友是贏家。
示例 2:
輸入:n = 1
輸出:true
示例 3:
輸入:n = 2
輸出:true
提示:
1 <= n <= 2e31 - 1
博弈論
在不知曉博弈論結論前,可以先通過找規律得到猜想,然后再從「何種情況下,先手會處于必勝態」的角度來進行分析。
根據題意,我們嘗試從小范圍數據的情況進行討論:
- 如果落到先手的局面為「石子數量為 - 」的話,那么先手必勝;
- 如果落到先手的局面為「石子數量為 」的話,那么先手決策完(無論何種決策),交到后手的局面為「石子數量為 - 」,即此時后手必勝,對應先手必敗(到這里我們有一個推論:如果交給先手的局面為 的話,那么先手必敗);
- 如果落到先手的局面為「石子數量為 - 」的話,那么先手可以通過控制選擇石子的數量,來使得后手處于「石子數量為 」的局面(此時后手必敗),因此先手必勝;
- 如果落到先手的局面為「石子數量為 」的話,由于每次只能選 - 個石子,因此交由后手的局面為 - ,根據流程 我們知道此時先手必敗;
到這里,我們猜想 當起始局面石子數量為 的倍數,則先手必敗,否則先手必勝(即 n % 4 != 0 時,先手必勝)。
代碼
public boolean canWinNim(int n) {if(n <= 3){return true;}return n % 4 != 0;}
上期經典算法
leetcode-413. 等差數列劃分