Nim游戏
全部抄的百度百科。自己做一些笔记……
我觉得百度百科这一篇文章写的挺好的,只是最后一段不得不涉及到学术内容。前面的一部分都是可以给不做学术的人看懂的。比百度百科其它某些文章,看上去高大上实际上有没有用的东西高到不知道哪里去了。
Nim游戏
有若干堆石子,每堆石子的数量都是有限的。游戏双方在操作的时候,可以选择一堆石子,并拿走若干石子(但是不能不拿)。直到一方无法操作(即全部被拿完)。无法操作的一方为败。
必胜策略
假设现在我们操作,讨论我们面临的局面,看我们是否有必胜策略。
先看看一种必胜的方法:
如果只有一堆石子,显然我们直接拿走这一堆石子就可以取胜。
如果有两堆石子,我们先拿走较大的那一堆多出来的石子。之后对方从第一堆石子拿走多少,我们就从第二堆石子拿走多少。这样我们也是必胜的。
(当然,如果两堆石子相等,对方有必胜策略)
如果有三堆……
感觉有点头疼。那么我们从另一个角度来看此问题。
局面分析
假设我们现在面临的是(3,3)这样一个局面。
(3,3)可以通过我们移动一次得到的局面有(0,3) (1,3) (2,3)。
接下来对方通过移动一次,从(0,3)会达到(0,0) (0,1) (0,2)。由于(0,0)是我方必败,因此如果对方面临的局面是(0,3),那么我方必败。
同理可以得到(1,3)与(2,3)都是我方必败的局面,因此(3,3)是我方必败的局面。
我们把(3,3),(0,0)这样的局面称之为先手必败局面,简称为必败局面。把(0,1) (0,2)这样的局面称之为先手必胜局面,简称为必胜局面。
那么我们也理论分析出了(3,3)是必败局面。同样,我们可以归纳得到,对于任何a=b,局面(a,b)为必败局面。
第一种方法
我们发现,对于一个局面的分析——
如果可以推导出的局面全部是必胜局面,那么此局面为必败局面。
如果推导出了有一个局面是必败局面,此局面就是必胜局面。
那么很显然我们可以使用递归来计算。
由于大量状态的重复,我们可以通过记忆化搜索或者DP来处理这个问题。
对于一个(a[1],a[2]……a[k])的局面,我们需要一个O(a[1]*a[2]*……*a[k])的时间复杂度来求解。
一些相关内容
局面的转移是一个拓扑图(大概也算作一个偏序集?不太懂)。这个通过它可以DP得到是很容易理解的。
基于上面的理论,一个局面要么是必胜局面,要么是必败局面。
因为每一个局面都可以通过拓扑排序得到。而这个拓扑排序中只有这两种局面。
位运算
我们发现这个递归式十分有趣,有点像或运算(如果有一个是1,那么答案就是1,如果全部是0,那么答案就是0)。
虽然和或运算关系不大。毕竟这是递归式……
首先,全部是0的局面是必败局面。
我们把(a[1],a[2]……a[n])变为二进制。
10100101001
01001100010
正如上面一样。
接下来我们发现,一次移动就是选择一个数字,把二进制数上面的某一个1变为0,把后面的所有的数字任意变化。
先考虑1位的情况:
如果末位只有1个1,那么显然这个局面是必胜局面。
如果末位有2个1,那么显然这个局面是必败局面。
……
如果末位有奇数个1,那么下一步一定是偶数个1,此局面为必胜局面。
如果末位有偶数个1,那么下一步一定是奇数个1,此局面为必败局面。
这个通过归纳法我们可以得到。
接下来考虑两位的情况:
如果第二位上只有1个1,那么这个局面显然可以推导出一个必败局面。因为我们可以选择把第2位上这个1删去,在对应的第一位上选择0或者1,达到末位有偶数个1的局面。那么,“第二位只有1个1”就是一个必胜局面。
如果第二位上有2个1:
如果先手选择移动第二位上的1,那么就会移动到第二位上只有一个1的局面,即移动到一个必胜局面。(所以先手不会移动第二位上的1)
如果先手选择移动第一位上的1,那么我们讨论:
如果第一位上只有1个1。那么先手移动一次之后,后手面临的局面就是“第二位上2个1,末位没有1”的局面(显然这是一个必败局面)。那么这个局面推导出了一个必败局面,所以这个局面就是必胜局面。
如果第一位上有2个1,那么先手移动一次之后,后手面临的就是一个必胜局面。那么我们发现,这个“第二位上2个1,末位2个1”的局面推导出的所有局面都是必胜局面,这个局面就是一个必败局面。
通过归纳,我们不难发现,如果第二位上有2个1的时候,
对于第一位上奇数个1,此局面为必胜局面;
对于第一位上偶数个1,此局面为必败局面。
如果第二位上有3个1:
显然,我们可以通过删去第二位上的一个1,让这一位对应的第一位变为0或者1,达到一个“第二位上有2个1,第一位上有偶数个1的局面”,即可以推导出一个必败局面,那么,“第二位上有3个1”就是一个必胜局面。
如果第二位上有4个1,不难发现它是与“第二位上有2个1”的局面是一样的。如果第二位上有5个1,不难发现他是与“第二位上有3个1”是一样的。
……
于是对于第二位的分析,我们可以得出:
如果第二位上有奇数个1,那么此局面为必胜局面
如果第二位上有偶数个1,那么需要考虑第一位:
如果第一位上有奇数个1,那么此局面为必胜局面;如果第一位上有偶数个1,那么此局面为必败局面。
这个通过归纳法亦可得到。
接下来我们考虑三位的情况
接下来我们考虑更高位的情况……
其实最后不难分析出来:
如果某一位上有奇数个1,那么此局面为必胜局面。否则为必败局面。
那么这就是异或运算:
如果a[1]^a[2]^……^a[n]=0,那么此局面为必败局面。否则为必胜局面。