You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. 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.
For example, 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.
思路：這道題經(jīng)過推演便可了解規(guī)律，推演過程如下：
| 石子數(shù)量 | 自己贏否（YES or NO) | 理由 |
|---|---|---|
| 1 | Y | 簡單推演可得 |
| 2 | Y | 簡單推演可得 |
| 3 | Y | 簡單推演可得 |
| 4 | N | 簡單推演可得 |
| 5 | Y | 可以自己拿1個干发，剩下的4個榛瓮，相當(dāng)于對方先拿必輸京腥，故我贏 |
| 6 | Y | 自己拿2個岔乔，剩4個叫编，原理同石子數(shù)量為5 |
| 7 | Y | 自己拿3個等缀，剩4個矛渴，原理同石子數(shù)量為6 |
| 8 | N | 不論自己拿1，2颅停，3個谓晌，剩下5，6癞揉，7個纸肉，都相當(dāng)于對方先拿，這樣對方贏喊熟，自己輸 |
| 9 | Y | 自己拿1個柏肪，剩下8個，相當(dāng)于共有8個石子芥牌，對方先拿烦味，對方必輸，我贏 |
| 10 | Y | 自己拿2個壁拉，剩下8個谬俄，相當(dāng)于共有8個石子，對方先拿弃理，對方必輸溃论，我贏 |
| 11 | Y | 自己拿3個，剩下8個痘昌，相當(dāng)于共有8個石子钥勋，對方先拿，對方必輸控汉，我贏 |
| 12 | N | 不論自己拿1笔诵，2返吻，3個姑子，剩下11，10测僵，9個街佑，都相當(dāng)于對方先拿，這樣對方贏捍靠，自己輸 |
故綜上所述沐旨，每當(dāng)石子數(shù)量是4的倍數(shù)的時候，都是自己輸榨婆，否則自己必贏磁携。
代碼如下
class Solution {
public:
bool canWinNim(int n) {
if(n%4 == 0){
return false;
}else{
return true;
}
}
};
