physixfan

Nim游戏的必胜策略和Xor运算的神奇应用

上一篇日志里介绍了Nim游戏，他的必胜策略可不是那么好想的。这个游戏貌似很久以前就已经有了，可是必胜策略直至20世纪初才被哈佛大学的一个叫做Charles Leonard Bouton的数学家找到，可见其思维难度；可是，这个必胜策略却只要由一个运算就搞定了：Xor(异或)运算，可见Xor运算之神奇。没有好好学过程序设计的人估计对Xor运算不甚熟悉，更不可能知道他的神奇应用了，因此我先说一说Xor运算。

Xor运算是位运算的一种，和And、Or运算类似，假如a、b都是布尔变量，则a Xor b被定义为：a、b相异则为真(所以中文名字叫做异或)，a、b相同则为假。其真值表为：1Xor0=1, 0Xor1=1, 1Xor1=0, 0Xor0=0。众所周知，位运算也可以用于两个数之间，其定义就是把这两个数转化为二进制，然后一位一位的进行位运算。比如说1Xor4=(001)₂ Xor(100)₂=(101)₂=5。位运算除了具有交换律、结合律这样的普通性质之外，还有几条神奇的性质。

Xor运算的神奇性质之一，就是他自己是自己的逆运算，即对于任何两个布尔变量或者数有(a Xor b)Xor b=a。这一点可以从真值表直接验证。有了这样一个性质，我们就可以把交换两个数的函数swap改进一下。大家应该都知道swap可以这么做：

void swap(int a, int b)

{a=a+b; b=a-b; a=a-b;} 

现在我们知道了Xor运算是本身的逆运算之后，就可以把上面的函数改成这个样子：（在C/C++里面把Xor表示为^）

void swap(int a, int b)

{a=a^b; b=a^b; a=a^b;}

乍一看肯定会觉得这个交换函数写的非常诡异，但是仔细一看就知道其原理和刚才那个是一模一样的。而且因为计算机在执行位运算的时候肯定比加减法要快，所以用Xor写的交换函数实际上还更快呢。

这里有一个有意思的小问题：现在给你2n+1个正整数，其中有n对数和1个单独的数，（这里规定一对数的意思是这两个数相等），然后让你设计一种算法，把这个单独的数给找出来，要求时间复杂度为O(n)。比如说这2n+1个数是1 2 …

拈游戏

所谓拈游戏的规则是这样的：（在看了沙发的评论之后我才知道其标准名字应该是Nim游戏…）

桌面上有三行硬币，每一行中分别有a1、a2、a3个硬币，其中a1、a2、a3是可以任意指定的正整数。两个人轮流拿走硬币，每一次只能从某一行中拿走任意多个硬币，谁拿走最后一枚硬币谁就赢了。

比如说a1=1,a2=2,a3=3的情况吧，这时如果轮到我拿了，我可以从第三行拿走2枚硬币，或者可以把第三行的三枚硬币全都拿走，等等；但是我不能同时从第一行和第三行里各拿走1枚硬币。这个简单的情况，可以枚举所有可能性得出结论：先拿的必输。

当a1、a2、a3是任意给定的，在什么情况下先拿的必输呢？必胜策略是怎样的呢？这是一个相当有意思的问题，答案可绝不是显而易见一目了然的。而当我当年看到这个策略长什么模样之后，完全的叹服了。今天我就先不写必胜策略了，大家可以先自己想想，如果下周或者什么时候有时间了再来写。前一阵子我为了熟悉C++自己写了一个拈游戏的人机对弈程序，大家可以点击下面的链接下载。其中包含了必胜策略，所以只要你一步走错就一定会输。

拈游戏.rar

其实拈游戏不仅仅局限于三行硬币，其实最初的问题是N行的，而且神奇的是其必胜策略对于任何N都是一样的。其实这个拈游戏是我上小学的时候奥数老师跟我玩的游戏，最近才发现这个经典的有意思的游戏还有好多人没有玩过，故写此文……

猫捉老鼠问题

这个是我室友的力学老师留给他们的思考题，因为它完全符合思维过程相当困难、但是解答却极为漂亮简单的原则，所以我就转过来分享一下。

在数轴上，0的位置停着一个不动的老鼠，1的位置在初始时刻有一只猫。猫是可以走动的，每一步在数轴上分别以二分之一的概率或朝着正方向或朝着负方向走1的距离。当猫到达0的位置时，猫就抓到老鼠了，游戏结束。问当猫走的步数趋向于无穷大的时候，最终捉到老鼠的概率是多大？一定要先仔细思考再看解答……

直上九宵的指数方程

有一道很简单的小问题：求解方程

$$\Large x^{x^{x^{x^{…}}}}=2$$

这样的方程解起来是很简单的，因为最低下的x的指数是他本身，即它的指数是2，因此该方程等价于x^2=2，立刻解得x=√2。

但是，如果题目地形式稍微一变，变成这个样子：

$$\Large x^{x^{x^{x^{…}}}}=4$$

用同样的方法你将会得出同样的答案x=√2。

现在问题来了，既然如此，那么表达式

$$\Large \sqrt 2^{\sqrt 2^{\sqrt 2^{\sqrt 2^{…}}}}$$

到底等于几呢？2还是4？…

有趣的无规行走模型

昨天和一帮子同学出去玩，晚饭时间点完菜等待上菜的时候有两个同学玩起了一个非常无聊的游戏：甲同学扔硬币，乙同学猜正反面，如果乙猜对了则乙的鼻子变长1cm，反之如果乙猜错了则鼻子缩短1cm。（这个是和谐过的版本，原始版本变长变短的不是鼻子而是另一个猥琐的东西…）。他们正在无聊的玩，全然不知道这么玩下去他鼻子长度的绝对值期望是多少…其实，这正是我高一的时候在费恩曼物理学讲义上看到的一个数学模型：Random Walk（无规行走）。对于这个模型，我敢说绝大多数人凭直觉会觉得鼻子长度的绝对值最终的期望值会是0，但事实绝非如此，你可以自己扔几次硬币试试，正确的答案应该是你扔硬币次数N的平方根！

下面给出证明，该证明基本来自《费恩曼物理学讲义》第一卷：…