Nim 游戏（292）

上一篇是为大家分享了一道打着“脑筋急转弯”tag的题目，然后我顺便就把这个类型的题目全部筛选出来看了看，发现总共没几个，所以就想的干脆一次全部讲完吧。

PNG

01、题目示例

这个类型的题目，其实除了废话多一点，好像没什么特别的。


第292题：Nim 游戏
你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。 你们是聪明人，每一步都是最优解。编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

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


PS：建议大家停留个两分钟先想一想…直接拉下去看题解就没什么意思了。

02、题目分析

这种问题，如果没有思路，可以先自己找个纸写写画画，找找规律


首先如果石头数小于4个，那么因为你是先手，一把拿走，肯定会赢。

PNG

而如果石头是4个，那不管你是拿了1,2,3个，最后一个都可以被你的对手拿走，所以怎么样都赢不了。

PNG

再继续分析到8个石头：对于5,6,7而言，你只需要对应的拿走1,2,3，然后留下4个，则对方必输。但是如果你要面对的是8，不管先拿（1,2,3）个，另一个人都可以通过 8-(1,2,3) ，使得你面对4个石头，则你必输无疑。通过观察，我们发现，好像是只要N是4的倍数，我们就必输无疑。

PNG

尝试性的写下代码：（这个，什么语言都无所谓吧….）

  1. //go
  2. func canWinNim(n int) bool {
  3.     return n % 4 != 0
  4. }

执行结果：

PNG

03、证明过程

脑筋急转弯的题目不是很多见，但是某些公司的某些人却钟情于此，如果是本着考察对方的思维能力，那我觉得还是挺好的。但若是为了寻找作为面试官的一丝丝优越感，那就只能是。。呵，打扰了。。


首先需要说下的是，这个问题属于博弈论。NIM的意思就是“尼姆”，并不是什么高大上的英文缩写。所以，NIM游戏一般也称之为尼姆游戏。说白了，就是设置两个对手，通过回合制的方式来玩的一种数学战略游戏，在早期网络不发达的时候很火。毕竟那时候连梦幻都没有，更别说王者。（非戏说，很多回合制游戏，其实本质就是数学游戏。而对于王者这种多人实时竞技游戏更是如此，如果想玩好，数学学不好，基本就凉凉。有兴趣的，可以了解一下游戏平衡师）


回到本题，假若对于先手有N个石头，那么后手的可能性有N-1，N-2，N-3三种。只有当后手的这三种可能性都必胜时，N才会必败。因为题目说了，我们都是聪明人（一般博弈论的问题都会有这句话），那如果后手的三种可能性中，有哪一种必败，作为先手，我们一定会走出这种可能性。那这种可能性是什么，其实就是让对方去面对4的倍数。如果先手我们遇到一个不是4的倍数的值x，有：

4k > N > 4(k-1)

N一定处于两个4的倍数之间，因为N本身不是4的倍数，那N距离最近的4的倍数的值最大为3。所以，只要我们不是面对4的倍数，作为先手，我们一定可以取走（12,3），使剩余的值变成4的倍数，则后手必输无疑。


所以，今天的问题你学会了吗？评论区留下你的想法！