题目

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. 在n分别为1,2,3时胜利，n等于4时失败，当n分别为5,6,7时，此时你只需取1,2,3块stone，则对方取时n都为4，此时对方失败；
2. 同理，当n等于8时，无论你取1,2,3块stone，对方都可以在7,6,5块stone里取，使剩余的stone数量变为4，从而赢得胜利；
3. 接下来可推得只要n为4的倍数，对方就取得胜利，否则我方获得胜利。

代码

func canWinNim(n int) bool {
    if n % 4 == 0 {
        return false
    } else {
        return true
    }
}