漫画：脑筋急转弯题目（尼姆问题求解）

今天是小浩算法“365刷题计划”第58天。昨天是为大家分享了一道打着“脑筋急转弯”tag的题目，然后我顺便就把这个类型的题目全部筛选出来看了看，发现总共没几个，所以就想的干脆一次全部讲完吧。反正我们还有307天....

01PARTNIM

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

你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

输入: 4

输出: false 

解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；

因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

（瞪一瞪就全部掌握）

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

02PART题目分析

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

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

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

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

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

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

（发现竟然神奇的通过了？）

郑重申明（读我的文章必看）：

• 本系列所有教程都不会用到复杂的语言特性，不需要担心没有学过相关语法，使用各语言纯属本人爱好。

• 作为学术文章，虽然风格可以风趣，但严谨，我是认真的。本文所有代码均在leetcode上进行过测试运行。

• 算法思想才是最重要的。

03PART证明过程

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

首先需要说下的是，这个问题属于博弈论。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的倍数，则后手必输无疑。

昨天的题目，还没有学习的，抓紧：

如果想看我其他骚操作的，可以看下面这些文章：

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

 小浩算法，每日一题

关注领取《图解算法》高清版

进群的小伙伴请加右侧私人微信（备注：进群）