NIM(2)“拈”游戏分析.pdf
《NIM(2)“拈”游戏分析.pdf》由会员分享,可在线阅读,更多相关《NIM(2)“拈”游戏分析.pdf(5页珍藏版)》请在文库网上搜索。
1、题目 1-12 NIM“拈”游戏分析 1 NIM“拈”游戏分析 问题 有 N块石头和两个玩家 A和 B, 玩家 A先将石头分成若干堆, 然后按照 BABA 的顺序不断轮流取石头,能将剩下的石头一次取光的玩家获胜。每次取石头时,每个玩 家只能从若干堆石头中任选一堆,取这一堆石头中任意数目(大于 1)个石头。 请问:玩家 A有必胜策略吗?要怎么分配和取石头才能保证自己有把握取胜? 解法与分析 据说,该游戏起源于中国,英文名字叫做“NIM”,是由广东话“拈”(取物之意) 音译而来,经由当年到美洲打工的华人流传出去,这个游戏一个常见的变种是将十二枚 硬币分三列排成 3,4,5 再开始玩 。我们这里讨论
2、的是一般意义上的“拈”游戏。 言归正传,在面试者咄咄逼人的目光下,你要如何着手解决这个问题? 在面试中,面试者考察的重点不是“what”能否记住某道题目的解法,某件历 史事件发生的确切年代,C+语言中关于类的继承的某个规则的分支等。面试者很想知 道的是“how”应聘者是如何思考和学习的。 所以,应聘者得展现自己的思路。解答这类问题应从最基本的特例开始分析。我们 用 N表示石头的堆数,M 表示总的石头数目。 当 N=1 时, 即只有一堆石头显然无论你放多少石头, 你的对手都能一次全拿光, 你不能这样摆。 当 N=2 时,即有两堆石头,最简单的情况是每堆石头中各有一个石子(1,1) 先让对手拿,无
3、论怎样你都可以获胜。我们把这种在双方理性走法下,你一定能够赢的编程之美微软技术面试心得 第1章 游戏之美 2 局面叫作安全局面。 当 N = 2,M 2 时,既然(1, 1)是安全局面,那么(1, X)都不是安全局面,因 为对手只要经过一次转换,就能把(1, X)变成(1, 1),然后该你走,你就输了。既然 (1, X)不安全,那么(2, 2)如何?经过分析,(2,2)是安全的,因为它不能一步变 成(1,1)这样的安全局面。这样我们似乎可以推理(3, 3)、(4, 4),一直到(X, X) 都是安全局面。 于是我们初步总结,如果石头的数目是偶数,就把它们分为两堆,每堆有同样多的 数目。这样无论
4、对手如何取,你只要保证你取之后是安全局面(X, X),你就能赢。 好,如果石头数目是奇数个呢? 当 M=3 的时候,有两种情况,(2, 1)、(1, 1, 1),这两种情况都会是先拿者赢。 当 M=5 的时候,和 M=3类似。无论你怎么摆,都会是先拿者赢。 若 M=7 呢?情况多起来了,头有些晕了,好像也是先拿者赢。 我们在这里得到一个很重要的阶段性结论: 当摆放方法为(1, 1, 1)的时候,如果 1 的个数是奇数个,则先拿者赢;如果 1 的个数是偶数个,则先拿者必输。 当摆放方法为(1, 1, 1, X)(多个 1,加上一个大于 1 的 X)的时候,先拿者必 赢。因为: 如果 1 有奇数个
5、,先拿者可以从(X)这一堆中一次拿走 X-1 个,剩下偶数个 1 接下来动手的人必输。 如果有偶数个 1,加上一个 X,先拿者可以一次把 X 都拿光,剩下偶数个 1 接下来动手的人也必输。 当然,游戏是两个人玩的,还有其他的各种摆法,例如当 M = 9 的时候,我们可以 摆为(2, 3, 4)、(1, 4, 4)、(1, 2, 6),等等,这么多堆石头,它们既互相独立,又 互相牵制,那如何分析得出致胜策略呢?关键是找到在这一系列变化过程中有没有一个 特性始终决定着输赢。这个时候,就得考验一下真功夫了,我们要想想大学一年级数理 逻辑课上学的异或(XOR)运算。异或运算规则如下: 编程之美微软技术
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- NIM 游戏 分析