python上的小火柴游戏必胜法 |
您所在的位置:网站首页 › python取火柴游戏 › python上的小火柴游戏必胜法 |
一.问题引入 小火柴游戏 在场上有三堆火柴(更普遍的情况史若干堆,但在这里先考虑三堆的情况),两名玩家轮流从三堆中选一堆,并取出任意根火柴,不能不取,只能取一次,两名玩家轮流进行游戏,取走最后一根火柴(取走最后若干根火柴则视为“内含”最后一根火柴)的玩家获胜,求必胜的方法。 二.自主探究问题 Ⅰ小火柴游戏 (1)规定和术语 一、场面(?,?,?):括号内表示三堆火柴分别的数量,用逗号隔开,没有顺序,如(1,2,3)表示一种场面。 二、行动:玩家从三堆中选一堆,并取出任意根火柴,不能不取,只能取一次。 三、我方行动结束后,达成的场面(?,?,?)使得我方获胜,则称之为利己场面T;反之,使对方获胜的场面成为利他场面F。 (2)经观察可以得到,当三堆火柴数量为(1,1,0)时,如果轮到对方行动,那么我方必然获胜,如果我方行动,那么我方必然失败。 (3)思路一:已知(1,1,0)为利己场面,那么(1,1,1)为利他场面,即有些利他场面可以固定地转化为利己场面,那么我们只要找出所有的利己场面并尽力保持作出利己场面就可以获胜了,实际上是通过上一个场面与下一个场面的递推关系来创造一条获胜的“行动链”来保证100%获胜。经过两个多周的“枚举”,我们找到了一个表格,其中是已经通过枚举验证,或者通过规律推测出的利己场面(表一)。 表一(横轴与纵轴以及对应的格子内所表示的三个数为我们找到的利己场面)这种方法是我们最初的思路,但有很多缺点: 1. 太过繁琐 2. 容易出错 3. 玩游戏时还要拿着这么大一张表 4. 无法从理论张证明我们已经找到的所有情况。 三.网络查询 为了解决问题我们从网上找到了一些资料,但都不全,有个资料提到了“二进制”,于是我们把二进制作为未来的研究方向。 四. 问题解决 1.通过对已知的利己场面进行二级制展开,我们发现: 如(1,2,3)可分解为(2º,2¹,2º+2¹) (7,12,11)可分解为(2º+2¹+2²,2²+2³,2º+2¹+2³) …… 经过研究发现表中的数都符合下面这个规律 表中的所有数(表中可能有错误的)在二项式展开后,都满足:三个数的二项式种类都成对存在。 例如:(7,12,11)可分解为(2º+2¹+2²,2²+2³,2º+2¹+2³)中 有两个2º、2¹、2²、2³,我们成这种关系为二项式展开都成对存在(CD)。 2.在这个结论出现一年之后,我发现了从理论上证明这个结论正确性的方法: 条件: 1. 所有的十进制数都可以用二进制数表示,且他们都一一对应。 2. 每一位玩家取火柴的时候,都只能改变三堆火柴中的一堆。 3. 改变之后的数字无论是十进制数还是用二进制数都会与原来不同。 推理: 利己场面(1,1,0)=(2º,2º,0)它也是符合CD规律,成为T0。 当一个场面符合CD时,他为二项式展开都成对存在(CD)。 例如:(7,12,11)可分解为(2º+2¹+2²,2²+2³,2º+2¹+2³) 我们可以发现(A,B,C)三个位置的互相关系是:知道其中任意两个数字,可以求另外一个数字。 形象证明:(二进制数)0111=7 1100=12 1011=11 也就是说,任意一堆对其他两堆来说都是固定的。(定义新运算※:两个二进制数相※的时候,相同的数级会消失,不同的数保留。例如:100100※111110=011010) 可得到:任意A※B=C,则(A,B,C)符合二项式展开都成对存在(CD) 那么当改变其中一堆时,由于这一堆本来的数量是符合二项式展开都成对存在(CD)的,所以当它改变之后就一定不符合CD,也就是利己场面不可能被对手转化为利己场面,即T不能转化为T。 一个F不满足二项式展开都成对存在(CD),但我们可以选择一堆,且总能让F转化为T,也就是说所有的F可以转化为T 形象证明:(二进制数)0111=7 A 1100=12 B ?可求, A※B=C 那么T0不能由任何T通过行动转化而来,所以当我方作出T的时候,对方永远不能将T转化为T(我方作为T,F情况的参照),对方只能将T转化为F,而我方总有办法将F((1,0,0)除外)通过行动转化为T,所以对方不可能达成T0,那么对方不可能赢,由于这场游戏一定有赢家,所以我方必赢。 所以通过这种方法,只要在游戏开始的时候我方面对的场面不是T,就总能胜利。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |