|
玩某些游戏靠的全是运气。你获胜的机会取决于骰子掷的点数或者是你抽到的好牌。但存在一些只靠策略取胜的游戏：如果你玩的足够机智，你就保证能赢。 一个强有力的实例就是很早就有的Nim游戏。不管你进行到了游戏的哪一步，对两名玩家的其中一个总存在一个取胜的策略。并且一个很巧妙的 告诉你是哪位玩家将有取胜策略。 Nim游戏的规则 传统的Nim游戏是对一些放置成堆的一定数量的硬币开始的：硬币和堆的数量取决于你。有两名玩家玩这个游戏，当轮到某位玩家时，他能从某一堆里取任意数量的硬币，但是至少要取一枚硬币，但是也不能从除你取的这个堆以外的其他堆里再取硬币。赢家是取得最后一枚硬币的人，所以最后是没有硬币剩余的。(一些人玩这个游戏的另一个版本是以取得最后的硬币的人为败者，但我们暂时忽略这个版本。) 玩这个游戏很明显没有运气成分。通过准确预测对手随后的一系列行动后，你能由此得到取硬币最好的策略。 作为对这个游戏的说明，假设有三堆分别有3,4,和5个硬币的堆。下面是这个游戏进行的一例：
上面的例子是以玩家A胜利而告终。我们感兴趣的问题是：给定一定初始量的堆和硬币，是否存在对某人的必胜策略？也就是说，如果某人走对每一步，他是否一定能赢。 让我们从举一些例子开始，两玩家分别称为A和B，假设A先走。一共两堆各有一枚硬币。那么显然，玩家B必胜：A必须取两个硬币里的一个，留下一个被B取走。 如果现在的两堆分别有2和1个硬币。现在玩家A有必胜策略：从有两个硬币的那堆取一个。这样造成的局面和上面的例子等同，我们知道这时A会赢。 再继续深入点：现在两堆各有两个。玩家B有必胜策略。如果A取走了一整堆，那么B只要取走剩余的那堆就赢了。如果A取走了一堆里的一个那么我们又回到了上一个例子的情况，只是这时B先走了。因此B保证能赢如果他从二硬币的堆里取一个。
从这一系列例子里你可能不由自主的发现了一些规律：存在一个巧妙的技巧能告知你对于任何给定的堆和硬币是否存在对某玩家的必胜策略。美国数学家Charles Bouton（1869-1922）同样感觉到这点并促使他毫不畏惧的开始分析这个游戏。在1902年他找到了这个窍门——及其精妙！为了搞清楚为什么对某位玩家会有必胜策略，你首先要...... 用Nim的方法来做加法运算 秘密就是把堆的大小用二进制数来表示（我假设读这篇文章的人都有一定的数学功底，只要稍微懂点电脑应该懂得二进制）。得到这个取胜秘密的取决于把堆的大小写成二进制形式，接着把这些数字加起来——但是别用一般的加法运算，准确的方法应该叫做Nim加法（Nim addition）。 为了准确的使用Nim加法加一些给定的二进制数，你先把它们排成行的写下来，就像你要做的加法运算一样。接着你轮流看每一列。如果1s的个数是奇数个，在它下面写一个1；如果偶数个，写个0.对每一列都进行这样的操作，得到的就是Nim加法的结果。 作为例子，让我们用Nim加运算加10,11和100（十进制下分别为2,3,4）： 10 11 100 —— 101 这个被称为Nim和（Nim sum）的结果是101。Nim加法和普通加法和普通加法不同在于：二进制的101表示十进制5，和原来那些数字之和2+3+4=9不相等。 谁赢了？ 当Charles Bouton分析了这个Nim游戏，他分析出了两个两个取得获胜策略的关键事实。 事实一：假设轮到你行动了，这时堆里的Nim和为0。这样不管你怎么做，你动作后的Nim和不会等于0. 事实二：假设轮到你行动了，这时堆里的Nim和不为0。但是可以保证的是，存在一种取法能在你行动后的堆的Nim和为0。 证明这些事实并不难，但是你也可以试着自己玩一下这个游戏来让自己相信。 现在如果你是玩家A，所以你先走。接着假设现在堆里的Nim和不等于0.你的策略将会是这样:如果可能尽可能使得下一个Nim和，也就是你动作后的Nim和为0.这也意味着无论B如何动作通过事实1可知，B的这个动作会把下个Nim和变得不为0. 让我们开始，在表中记录每一步的Nim和：
这个像乒乓球一样的Nim和不断在0和非0之间转化，意味着你保证能赢！如果B注定要赢，她将要把最后一个硬币攒在手中。也就是说：她需要一个动作来产生零Nim和，但在我们看来这是不可能的。你的每次动作，都在把Nim和减少到0。当游戏进行到快到结尾时时，零Nim和就等价于没有一个硬币剩余——这时你就赢了。 这说明以非零Nim和打头的游戏，玩家A都有一个必胜策略。策略就是在每一步都让下一个Nim和减少到0. 如果游戏开始时为零Nim和，那么玩家B有一个必胜策略。当轮到B动作时不管玩家A在第一步做了什么将会留下一个非零Nim和。那么按同上的理由，必胜策略掌握在了B的手中。 Nim加法统治世界 Nim加法在你玩Nim游戏的时候很有用，但仅仅是这样吗？错！事实证明我们每天的生活都依赖于这种奇怪形式的加法。 计算机是二进制机器。所有储存的信息，包括数字都是被转化成一串串0s和1s。但是计算机斌不只是储存信息，它还执行逻辑运算，基于是/否的答案。比如，给定一个用户的账号和密码，它们需要知道账号是否正确和密码是否正确这些问题。根据答案来决定是否让此人登陆。注意这个操作需要两个输入（用户名正确吗？密码正确吗？）并返回一个输出（允许登陆或不允许登陆）。 用0表示否，1表示是这些逻辑操作又能被转换为涉及0s和1s的操作。幸运的是，事实上任何你想执行的逻辑运算都是由六种基本操作组成。你只要按需把它们组合即可。 六个中的其中之一被称为异或。这个运算也是需要两个输入，可以是0或1，返回一个输出值，也可以是0或1.下面是异或操作的具体说明：
更仔细观察会发现异或和Nim加法是等价的：
所以很多计算机执行的操作都基于Nim加法——没有它，事情将会变得不一样。 译自—— plus.math.org |
|
|
来自： 雪柳花明 > 《LeetCode》
