Problem

你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

e.g.

输入: 4
输出: false 
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

Solution

考虑轮到玩家的时候，如果桌子上只剩下1-3个石头，那么必然会赢，如果剩下4个石头，那么怎么拿都会输。接下来考虑剩下多于4个石头的时候，如果能够采取操作让对手面临轮到他的时候只剩下4个 石头，则可以赢，那么易知在剩下5-7个石头的时候满足上述情况，可以赢。接下来考虑剩下8个石头的时候，此时无论采取什么操作，到对手轮次的时候必然只会剩下5-7个石头，这个时候对手必然能赢，按照这个规律可以一直推下去，得到当桌子上剩下4k+1, 4k+2, 4k+3个石头的时候当前玩家必然能赢，剩下4k的时候必然会输，得到一行代码

bool canWin(int n) {
    return (n % 4) != 0;
}