LeetCode 292. Nim Game

题目

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.

Example:

Input: 4
Output: false 
Explanation: 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.

解析

题目大意还是比较好理解的，下面稍微扩展一下：
假设一堆里面有n个石头，每次可以取1-m个石头。
（1）若n=m+1，则先取者无论取多少石头，后取者都可以拿走所有的石头。先取者必输；
（2）若n=k(m+1)，若先取者先取k(1<k<m)个石头，则后取者取m+1-k个石头就达到平衡，这样先取者也必输；
（3）若n=k(m+1)+s，那么先取者先取s（s>1 && s%(m+1)!=0）个石头后n为k(m+1)，回到了第二种情况，就转化为第二个人先取，这样第一个人必赢。
因此代码就很容易了。

代码（C语言）

bool canWinNim(int n) {
    return n % 4 ? true : false;
}

有兴趣的老铁可以扩展解决一下Nim Game原型，Nim博弈。