你和你的朋友,兩個人一起玩 Nim 游戲:桌子上有一堆石頭,每次你們輪流拿掉 1 - 3 塊石頭。 拿掉最后一塊石頭的人就是獲勝者。你作為先手。
你們是聰明人,每一步都是最優解。 編寫一個函數,來判斷你是否可以在給定石頭數量的情況下贏得游戲。
- 示例:
輸入: 4
輸出: false
解釋: 如果堆中有 4 塊石頭,那么你永遠不會贏得比賽;因為無論你拿走 1 塊、2 塊 還是 3 塊石頭,最后一塊石頭總是會被你的朋友拿走。
這道題是一道純推理題,最紅的結果是,如果剩余 n
為 4 的倍數,則,先手必輸,否則先手必贏。為什么呢?
其實很簡單,如果剩余 4,則無論先手如何取,剩余都會在 1-3 之間,后手可以一次取完,結局注定失敗!
所以,如果此時,剩余數量為 4 的倍數,則無論先手如何取,后手都可以控制每次遞減的數為 4。
而如果先手時,數量為 4n + k, 1 <= k <=3,則先手可以直接將 k 去掉,剩余 4n,后手在取石頭的時候,面臨的是 4n,則其必輸。
代碼如下
class Solution {
public:bool canWinNim(int n) {if (n % 4 == 0) {return false;} else {0return true;}}
};