【每日一道智力题】之轮流取石子(尼姆博弈的详解）

小灰灰 2024-03-30 17:52 60阅读 0赞

> 博客主页：[张栩睿的博客主页][Link 1]
> 
> 欢迎关注：点赞+收藏+留言
> 
> 系列专栏：[c语言学习][c]
> 
>  **家人们写博客真的很花时间的，你们的点赞和关注对我真的很重要，希望各位路过的朋友们能多多点赞并关注我，我会随时互关的，欢迎你们的私信提问，也期待你们的转发！**
> 
>  **希望大家*****关注我，*****你们将会看到更多精彩的内容！！！**

### 前言： ###

在昨天的每日一题里面，我们对于尼姆博弈相关的问题有了一定的了解[简单的尼姆博弈][Link 2]，今天我们就来进一步了解这个博弈。

### 母题： ###

有若干堆石子，每堆石子的数量是有限的，二个人依次从这些石子堆中拿取任意的石子，至少一个（不能不取），最后一个拿光石子的人胜利。【两人都非常聪明】——博弈论必备条件。

### 解析： ###

1、我们首先以一堆为例： 假设现在只有一堆石子，你的最佳选择是将所有石子全部拿走，那么你就赢了。

2、如果是两堆：假设现在有两堆石子且数量不相同，那么你的最佳选择是取走多的那堆石子中多出来的那几个，使得两堆石子数量相同，这样，不管另一个怎么取，你都可以在另一堆中和他取相同的个数，这样的局面你就是必胜。比如有两堆石子，第一堆有3个，第二堆有5个，这时候你要拿走第二堆的三个，然后两堆就都变成了3个，这时你的对手无论怎么操作，你都可以“学”他，比如他在第一堆拿走两个，你就在第二堆拿走两个，这样你就是稳赢的。

3.假设只有两堆石子。那么，当两堆石子数量相等的时候，先手是必败的。

很好！我们已经找到了一个非常非常牛逼的规律！当两堆石子数量相等的时候，先手必输！

没错，大家一定都可以想懂这几步，但是以下的第4步我就有点看不懂了(可能是我太菜了)

> 4.如果是三堆 ，我们用（a，b，c）表示某种局势，首 先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是 （0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一  
> 下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情型。  
> 从中我们要明白两个理论：
> 
> **一个状态是必败状态当且仅当它的所有后继都是必胜状态  
> 一个状态是必胜状态当且仅当它至少有一个后继是必败状态**
> 
> 有了这两个规则，就可以用递推的方法判断整个状态图的每一个结点都是必胜还是必败状态。
> 
> 这里引入L . Bouton在1902年给出的定理：**状态（x1,x2,x3）为必败状态当且仅当x1 XOR x2 XOR x3=0，这里的XOR是二进制的逐位异或操作，也成Nim和。**

其实吧，这个尼姆博弈基本上都是一句话：“**也不知道是谁这么牛逼把这个东西和[二进制][Link 3]联系在了一起”**，要么就是大佬一句话带过地写了一下异或或者尼姆和即可！

那么我们再来想这么一个问题，假设存在有第三堆石子，前两堆石子的数量相同，最后一堆石子数量不同，比如1，1，3，我们看一下，此时A同志又可以必赢，这是为什么呢？我们可以发现，第三堆石子A可以直接拿走，转化成了B先手，两堆石子数量一样的情况。

那么如果是1，1，1的情况呢？你很容易发现A其实必赢。

好了，情况列举就到这里，接下来我们要开始进行推导了。

由【任意两堆数量相同的石子博弈情况为先手必输】再加上1，1，1情况先手必赢，我们开始进行总结。

我们在取第三堆石子的时候要考虑到前两堆石子的输赢情况，当然这里取石子的方法，顺序我们并不能决定，我们只是计算有没有必赢的情况。

现在！一个牛逼的家伙要把这个东西和二进制联系到一起了！

我们知道，石子的数量肯定是非负整数，那就肯定有其二进制表示！

比如两堆石子数量分别为7和5。

二进制分别为：111和101。那么7就可以看作为4+2+1，5可以看作为4+1。对！二进制拆分！

111=100+10+1，101=100+1。

换成十进制就是：

7=4+2+1，5=4+1。

现在！石子的堆数变了！不是两堆！是五堆石子！其中两堆的数量为4，两堆为1，这两堆里先手可以必输，然后最后一堆数量不管多少直接拿走取得胜利！

至此就解释了为什么这个东西可以和二进制联系在一起。

那么再解释一下这个鬼东西为什么要和二进制联系在一起。因为我们看到上述变形里面我们知道了数量为4和1的那几堆使得先手在那里必输，那么我们可不可以在二进制运算里面把他们直接归零不计呢？

对！可以！用异或就很简单！而且在C语言里面可以直接写出来异或运算！方便快捷还省事儿！而且人家直接就是按照二进制去算的！这一步就直接把转换二进制什么的全给做完了。

按照上述例子，7和5，异或计算过后答案是2。答案是2！这个2何其熟悉！如果两个数字相同异或结果为0的话，先手必输。反之不为0就先手可以必赢。0为假非0为真！而且异或后的结果是什么呢？是去除了所有二进制拆分后数量相等的石子堆之后还剩余的石子。

下面我们再来扩展一下，n堆石子的情况。

假设n为3，三堆石子数量分别为a，b，c。

如果我们a^b==0那么c只要不为0的话先手就可必赢。

所以，如果a^b^c!=0，A就可以必赢。为什么呢？我们把ab合成一堆去看，会发现这时问题简化成为了两堆石子。两堆石子！也就说两堆石子只要数量不同就可以！（按位异或有交换律）

同理，n=1,2,3,4,5...都可以。只要a^b^c^d^.......!=0，那么A就可必赢！

下面是该题目实现的代码：

#include<stdio.h>
    int main()
    {
    	int n,a=0,b;//初始化a为0为了保证不管异或谁都可以
    	scanf("%d", &n);//数字个数
    	while (n--)
    	{
    		scanf("%d", &b);
    		a ^= b;//异或！！！
    	}
    	printf(a ? "YES\n" : "NO\n");//最后判断输出即可
    	return 0;
    }

这就是今天的每日一道智力题，对于尼姆博弈的简单介绍就到这里了。辛苦各位小伙伴们动动小手，三连走一波最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！在这里睿睿祝大家新年快来啦！

[Link 1]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[c]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 2]: http://t.csdn.cn/566ni
[Link 3]: https://so.csdn.net/so/search?q=%E4%BA%8C%E8%BF%9B%E5%88%B6&spm=1001.2101.3001.7020