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.
思路：这道题经过推演便可了解规律，推演过程如下：
| 石子数量 | 自己赢否（YES or NO) | 理由 |
|---|---|---|
| 1 | Y | 简单推演可得 |
| 2 | Y | 简单推演可得 |
| 3 | Y | 简单推演可得 |
| 4 | N | 简单推演可得 |
| 5 | Y | 可以自己拿1个，剩下的4个，相当于对方先拿必输，故我赢 |
| 6 | Y | 自己拿2个，剩4个，原理同石子数量为5 |
| 7 | Y | 自己拿3个，剩4个，原理同石子数量为6 |
| 8 | N | 不论自己拿1，2，3个，剩下5，6，7个，都相当于对方先拿，这样对方赢，自己输 |
| 9 | Y | 自己拿1个，剩下8个，相当于共有8个石子，对方先拿，对方必输，我赢 |
| 10 | Y | 自己拿2个，剩下8个，相当于共有8个石子，对方先拿，对方必输，我赢 |
| 11 | Y | 自己拿3个，剩下8个，相当于共有8个石子，对方先拿，对方必输，我赢 |
| 12 | N | 不论自己拿1，2，3个，剩下11，10，9个，都相当于对方先拿，这样对方赢，自己输 |
故综上所述，每当石子数量是4的倍数的时候，都是自己输，否则自己必赢。
代码如下
class Solution {
public:
bool canWinNim(int n) {
if(n%4 == 0){
return false;
}else{
return true;
}
}
};
网友评论