[leetcode解题报告]NimGame 题型汇总

最近在 leetcode 上面刷题，是的，没错，就是传说刷了150道题之后，就可以升天(欠揍！) 的网站。
今天从 easy -> hard 开始刷题，把相关的解题报告写出来，这样便于复习所用。

题目链接:
题目内容:

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.

题型分析:
这道题是归纳特点题型分析，找到数列排列的规律公式，在代码中使用公式来进行判断即可。

解题思路:
不妨设每次所给的所有石头数目为 n ， 是否能够获胜这一结果为函数 f(n)
根据题意描述便有了如下的公式：
f(1) = true ; 我首先动手，将1个石头拿走
f(2) = true ; 我首先动手，将 2 个石头拿走
f(3) = true ; 我首先动手，将 3 个石头都拿走
f(4) = false ; {1. f(1) + f(3) : 朋友在我拿走 1 个石头之后，将剩下的 3 个石头全部拿走} {2. f(2)+f(2): 我先拿 2 个石头，朋友拿 2 个}
                   {3. f(3) + f(1) : 我先拿走 3 个，朋友拿走 1 个}
                   无论是上述的那种情况，都是朋友获胜，这个是一定的

f(5) = f(1) + f(4) ; true , 我先拿走 1 个石头，将4个石头的情况交给朋友，只要是拿石头者遇到 4 个石头的情况，就一定会输
f(6) = f(2)+f(4) ;  true
...
f(n) = f(n%4)+f(...) ;

综上总结可以归纳出来，如果当前 n 石头总个数能够除4所得余数不为0 ，我首次取走余数部分，将剩余的 4 的倍数的部分交给朋友处理，
那朋友此次游戏一定是输掉的，如果 n %4 ==0 ,那我首次面对的情况便是4倍数个石头个数，那这次游戏输的一定是我。

解题代码:

class Solution {
public:
    bool canWinNim(int n) {
        if(n%4==0)
            return false ;
        else
            return true ;
    }
};

相关题型:
这道题有很多的变种题型，在 剑指offer，编程美 这两本书中都有所介绍

1. 如果将这道题改为，最后拿石头的人输掉，那应该如何解决呢？
那就是最后面对的若是 f(1) 这种情况的人，必定输掉，如果我们根据给定的 n 可以推知自己是否能够面对 f(1) 这种情形，那么便可以获知此次是否能赢得比赛了
n = 1, f(1)=1 : false
n = 2, f(2) = f(1) + f(1) : true
n = 3, f(3) = f(2) + f(1) : true
n = 4, f(4) = f(3) + f(1) : true

n = 5, f(5) = f(4) + f(1) : true
n = 6, f(6) = ; ; ;  无论拿 1-3 几个石头，都会将情形转换为 获胜的数目交给朋友，所以这种情况一定会输 false
n=7 ,  f(7) = f(1)+f(6) : true 这种情况，可以将 f(6) 必输的情形转给 朋友，这样朋友必输， true

综上总结就得出了，如果 n%6 ==0 || n ==1 , 那么此次比赛必输，其他的情况是必胜的


end