292. Nim Game (Easy)

链接：

题目：https://leetcode.com/problems/nim-game/
代码(github)：https://github.com/illuz/leetcode

题意：

很经典的博弈游戏，两个人从一堆石头中轮流取出 1-3 个石头，谁先取完谁就赢了。
你是先手，现在问如果石头有 n 个，你能不能赢。

分析：

这个游戏其实不管从推理还是从结论上说都和文章开头的游戏一样，不过这次我们尝试找出更普遍的规律。因为石子的数量总是递减的，所以这个游戏必将在有限步（15步）内结束。我们可以用余下石子的数目来表示局面，于是一共有16个局面。因为规定了拿走最后一个石子的人赢，换句话说当石子个数为0时，就是一个“轮到谁谁就输”的局面，我们通常叫这种局面为必败态。既然0是必败态，那么当局面为1,2,3时，先手就可以采取规则所允许的策略（拿走1个，2个，或是3个）来把局面变成0，于是称1,2,3为胜态；而当局面为4时，不论采取何种策略，局面都将走向胜态，从而4是一个必败态。

可以去了解下，入门：博弈入门：从数学游戏开始，进阶的就去看 Nim 的 Wiki 吧。

这题目可能有很多人看过，不过要讲清楚可能并不轻松。虽然解很简单，不过却是一道考察表达能力的好题。