leetcode 292 Nim Game

leetcode 292 Nim Game

题目翻译：

　　你正在和你朋友在玩Nim Game的游戏：桌子上有一堆石头，每次你们其中一个人只能取走1到3块石头，最后谁取走剩下石头的将会胜出。第一次将由你来先取石头。

　　你们两个都很聪明，都会采取最佳游戏策略。根据石头堆得数目，写一个函数求出谁最后胜出。

　　例如：石头堆有4块石头，你将永远赢不了。无论你第一次取1,2,3块石头，你的朋友将会取完剩下的石头。

解题思路：

　　这道题应该是很经典的题目了，难度的确不大。初中时有过类似的数学竞赛题，不过当时每次取走的是1,2块。

　　若对方先取石头，然后到我取，每一轮取走石头总数有如下可能：

　　对方取走1，我可取1,2,3，则一轮共可取走2,3,4；

　　对方取走2，我可取1,2,3，则一轮共可取走3,4,5；

　　对方取走3，我可取1,2,3，则一轮共可取走4,5,6；

　　对于任何一种对方的取法，我所有可能的取法中，唯一能确定的就是保证每轮消耗的石头数为4。当对方取石头的时候，石头数为4*n，即4的倍数，那么最后一轮开始的时候，剩下的石头数将是4，我将获胜。所以，总石头数为4n+1,4n+2,4n+3时，我首先取走1,2或3，我胜出，若总石头数为4n，我输。

代码：

 1 class Solution {
 2 public:
 3     bool canWinNim(int n) {
 4         if (n % 4 == 0){
 5             return false;
 6         }
 7         else{
 8             return true;
 9         }
10     }
11 };

leetcode 292 Nim Game

原文：http://www.cnblogs.com/lfwllq/p/5118065.html