国家集训队2002论文集张一飞.docVIP

  1. 1、本文档共16页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
由感性认识到理性认识 ——透析一类搏弈游戏的解答过程 一、 游戏 2 二、 从简单入手 2 三、 类比与联想 6 四、 证明 8 五、 推广 11 六、 精华 12 七、 结论 16 八、 总结 17 游戏 游戏A: 甲乙两人面对若干堆石子,其中每一堆石子的数目可以任意确定。例如图1所示的初始局面:共n=3堆,其中第一堆的石子数a1=3,第二堆石子数a2=3,第三堆石子数a3=1。两人轮流按下列规则取走一些石子,游戏的规则如下: 每一步应取走至少一枚石子; 每一步只能从某一堆中取走部分或全部石子; 如果谁无法按规则取子,谁就是输家。 图 1 游戏的一个初始局面 游戏B: 甲乙双方事先约定一个数m,并且每次取石子的数目不能超过m个; 其余规则同游戏A。 我们关心的是,对于一个初始局面,究竟是先行者(甲)有必胜策略,还是后行者(乙)有必胜策略。 下面,我们从简单入手,先来研究研究这个游戏的一些性质。 从简单入手 用一个n元组(a1, a2, …, an),来描述游戏过程中的一个局面。 可以用3元组(3, 3, 1)来描述图1所示的局面。 改变这个n元组中数的顺序,仍然代表同一个局面。 (3, 3, 1)和(1, 3, 3),可以看作是同一个局面。 如果初始局面只有一堆石子,则甲有必胜策略。 甲可以一次把这一堆石子全部取完,这样乙就无石子可取了。 如果初始局面有两堆石子,而且这两堆石子的数目相等,则乙有必胜策略。 因为有两堆石子,所以甲无法一次取完; 如果甲在一堆中取若干石子,乙便在另一堆中取同样数目的石子; 根据对称性,在甲取了石子之后,乙总有石子可取; 石子总数一直在减少,最后必定是甲无石子可取。 对于初始局面(1),甲有必胜策略,而初始局面(3, 3),乙有必胜策略。 局面的加法:(a1, a2, …, an) + (b1, b2, …, bm) = (a1, a2, …, an, b1, b2, …, bm)。 (3) + (3) + (1) = (3, 3) + (1) = (3, 3, 1)。 对于局面A, B, S,若S=A+B,则称局面S可以分解为“子局面”A和B。 局面(3, 3, 1)可以分解为(3, 3)和(1)。 如果初始局面可以分成两个相同的“子局面”,则乙有必胜策略。 设初始局面S=A+A,想象有两个桌子,每个桌子上放一个A局面; 若甲在一个桌子中取石子,则乙在另一个桌子中对称的取石子; 根据对称性,在甲取了石子之后,乙总有石子可取; 石子总数一直在减少,最后必定是甲无石子可取。 初始局面(2, 2, 5, 5, 5, 5, 7, 7),可以分成两个(2, 5, 5, 7),故乙有必胜策略。 对于局面S,若先行者有必胜策略,则称“S胜”。 对于局面S,若后行者有必胜策略,则称“S负”。 若A=(1),B=(3, 3),C=(2, 2, 5, 5, 5, 5, 7, 7),则A胜,B负,C负。 我们所关心的,就是如何判断局面的胜负。 如果局面S胜,则必存在取子的方法S→T,且T负。 如果局面S负,则对于任意取子方法S→T,有T胜。 设初始局面S可以分解成两个子局面A和B(分解理论)。 若A和B一胜一负,则S胜。 不妨设A胜B负; 想象有两个桌子A和B,桌子上分别放着A局面和B局面; 因为A胜,所以甲可以保证取桌子A上的最后一个石子; 与此同时,甲还可以保证在桌子B中走第一步的是乙; 因为B负,所以甲还可以保证取桌子B中的最后一个石子; 综上所述,甲可以保证两个桌子上的最后一个石子都由自己取得。 若A负B负,则S负。 无论甲先从A中取,还是先从B中取,都会变成一胜一负的局面; 因此,乙面临的局面总是“胜”局面,故甲面临的S是“负”局面。 若B负,则S的胜负情况与A的胜负情况相同。 若A胜B胜,则有时S胜,有时S负。 如果S=A+C+C,则S的胜负情况与A相同。 令B=C+C,则S=A+B且B负,故S的胜负情况与A相同。 图1所示的初始局面(3, 3, 1) = (3) + (3) + (1),与局面(1)的胜负情况相同。 图1中所示的初始局面(3, 3, 1)是“胜”局面,甲有必胜策略。 称一个石子也没有的局面为“空局面”。 空局面是“负”局面。 如果局面S中,存在两堆石子,它们的数目相等。用T表示从S中把这两堆石子拿掉之后的局面,则称“S可以简化为T”。 局面(2, 2, 2, 7, 9, 9)可以简化为(2, 2, 2, 7),还可以进一步简化为(2, 7)。 一个局面的胜负情况,与其简化后的局面相同。 三个局面(2, 2, 2, 7, 9, 9)、(2, 2, 2, 7)和(2, 7),胜负情况都相同。 不能简化的局面称为“最简局面”。 局面 (2, 7)是最简局面。 最简局面中不会有两堆相同的石子

文档评论(0)

185****7617 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档