292. Nim Game 尼姆游戲

You are playing the following Nim Game with your friend:
您正在和您的朋友玩以下NIM游戲：
There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones.
桌上有一堆石頭，你們中的每一個人輪流移動1到3塊石頭。
The one who removes the last stone will be the winner.
移走最后一塊石頭的人將是獲勝者。
You will take the first turn to remove the stones.
你將在第一個回合移動石塊。

Both of you are very clever and have optimal strategies for the game.
你們兩個都很聰明，都有最佳的游戲策略。
Write a function to determine whether you can win the game given the number of stones in the heap.
寫一個函數(shù)來決定你是否能在給定石頭堆數(shù)的情況下贏得比賽。

Example 例子

Input: 4
Output: false
Explanation: If there are 4 stones in the heap, then you will never win the game;No matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
說明：如果堆中有4塊石頭，那么你將永遠無法贏得比賽；無論你移除1塊、2塊或3塊石頭，最后一塊石頭都將被你的朋友移除。

思路

n=1,2,3時你贏，n=4時對手贏；

n=5時，根據(jù)上一點，你只需先拿走1個石子，于是剩下4個，由于“n=4時對手贏”，而對手的對手是你，因此你必贏；

n=6，7時同理；

n=8時，你有3種選擇，結(jié)果分別剩下7,6,5個石子，此時對手站在你的角度，根據(jù)上面結(jié)論，對手必贏。

……如何循環(huán)下去，你總是3贏1輸。

code

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

總結(jié)

以上是生活随笔為你收集整理的LeetCode 292. Nim Game的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。