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的倍数,则后手必输无疑。


所以,今天的问题你学会了吗?评论区留下你的想法!