292. Nim Game

• Total Accepted: 84580
• Total Submissions: 157260
• Difficulty: Easy

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.

每个人轮流拿桌上的石头，一次可以去1 或者2或者 3 个，谁拿到最后的一个石头就赢了。

假设 A 和  B两个人拿石头，假定A先拿。

1 2 3     4   5 6 7  8  9 10 11  12 13 14 15 

石头数目如果是红色标记的个数，那么A肯定可以赢，即赢得条件是 n % 4 == 0 。

这么理解，石头数为4个时候 A 必输，可是当石头个数为 1 、2 、3时候A必赢。所以当石头数目大于4而又小于8的时候，A可以策略性的让B拿取石头后，石头的数目分布在[1,3]之间，因为A知道只要石头数目在[1,3]区间他肯定会赢。当石头数目为大于8的时候，Ａ要策略性让B拿取石头后，石头的数目分布在[５,７]之间，因为A知道只要石头数目在[５,７]区间他肯定会赢，依次往后推．．．．。

1 bool canWinNim(int n) {2     if(n%4 == 0)3         return false;4     else5         return true;6 }