文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 取火柴游戏
侵权投诉

取火柴游戏

取火柴的游戏

题目1:今有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根, 可将一堆全取走,但不可不取,最后取完者为胜,求必胜的方法。

题目2:今有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根, 可将一堆全取走,但不可不取,最后取完者为负,求必胜的方法。

嘿嘿,这个游戏我早就见识过了。小时候用珠算玩这个游戏:第一档拨一个,第二档拨两个,依次直到第五档拨五个。然后两个人就轮流再把棋子拨下来,谁要是最后一个拨谁就赢。有一次暑假看见两个小孩子在玩这个游戏,我就在想有没有一个定论呢。下面就来试着证明一下吧

先解决第一个问题吧。

定义:若所有火柴数异或为0,则该状态被称为利他态,用字母T表示;否则, 为利己态,用S表示。

[定理1]:对于任何一个S态,总能从一堆火柴中取出若干个使之成为T态。 证明:

若有n堆火柴,每堆火柴有A(i)根火柴数,那么既然现在处于S态, c = A(1) xor A(2) xor … xor A(n) > 0;

把c表示成二进制,记它的二进制数的最高位为第p位,则必然存在一个A(t),它二进制的第p位也是1。(否则,若所有的A(i)的第p位都是0,这与c的第p位就也为0矛盾)。

那么我们把x = A(t) xor c,则得到x < A(t).这是因为既然A(t)的第p位与c的第p位同为1,那么x的第p位变为0,而高于p的位并没有改变。所以x < A(t).而

A(1) xor A(2) xor … xor x xor … xor A(n)

= A(1) xor A(2) xor … xor A(t) xor c xor … xor A(n)

= A(1) xor A(2) xor… xor A(n) xor A(1) xor A(2) xor … xor A(n) = 0

这就是说从A(t)堆中取出 A(t) - x 根火柴后状态就会从S态变为T态。证毕

[定理2]:T态,取任何一堆的若干根,都将成为S态。

证明:用反证法试试。

若

c = A(1) xor A(2) xor … xor A(i) xor … xor A(n) = 0;

c' = A(1) xor A(2) xor … xor A(i') xor c xor … xor A(n) = 0; 则有

c xor c' = A(1) xor A(2) xor … xor A(i) xor … xor A(n) xor A(1) xor A(2) xor … xor A(i') xor c xor … xor A(n) = A(i) xor A(i') =0

进而推出A(i) = A(i'),这与已知矛盾。所以命题得证。

[定理 3]:S态,只要方法正确,必赢。

最终胜利即由S态转变为T态,任何一个S态,只要把它变为T态,(由定理1,可以把它变成T态。)对方只能把T态转变为S态(定理2)。这样,所有S态向T态的转变都可以有己方控制,对方只能被动地实现由T态转变为S态。故S态必赢。

[定理4]:T态,只要对方法正确,必败。

由定理3易得。

第1页

你可能喜欢

  • 实训报告
  • 数据结构 校园导航
  • 火柴棍游戏
  • 奥数六年级
  • 数学小故事
  • 游戏源代码
  • 火柴棒游戏

热门文档

相关文档

  • P1186取火柴游戏

    从问题的描述分析,可以将问题中的 k 堆火柴棒抽象为 k 个非负整数,而每取一次火柴 棒可抽象为使其中的一个自然数变小,当所有的数都变为 0 时,游戏结束,...

  • 人机对战取火柴游戏源代码

    人机对战取火柴游戏源代码_计算机软件及应用_IT/计算机_专业资料。# include <iostream.h> # include # include <stdlib.h> int man(int m); int cmp(int...

  • ...背包型】rockers问题 3251 取火柴游戏

    3246 【动态规划进阶-背包型】rockers问题 3251 取火柴游戏 选填,简要介绍文档的主要内容,方便文档被更多人浏览和下载。选填,简要介绍文档的主要内容,方便文档被更多...

  • 火柴游戏

    北京理工大学珠海学院计算机学院 Java课程设计报告 题目: 火柴游戏 姓学专班学 ...2.2 图形用户界面设计 从 JLabel 类中创建三个标签, 填入指定文本表示人取的...

  • 火柴游戏

    火柴游戏_幼儿读物_幼儿教育_教育专区。趣味数学:火柴游戏 一个最普通的火柴游戏就是两人一起玩, 先置若干支火柴於桌上,两人轮流取, 每次所取的数目可先作一些...

  • 火柴游戏

    火柴游戏_育儿理论经验_幼儿教育_教育专区。火柴游戏一个最普通的火柴游戏就是两人一起玩, 先置若干支火柴于桌上, 两人轮流取, 每次所取的数目可先作一些限制,...

  • 火柴游戏

    火柴游戏_育儿理论经验_幼儿教育_教育专区。火柴游戏张晓霞 一个最普通的火柴游戏就是两人一起玩,先置若干支火柴于桌上,两人轮流 取,每次所取的数目可先作一些限...

  • 火柴游戏

    火柴游戏_教育学/心理学_人文社科_专业资料。1、 火柴游戏一: 用 9 根火柴做...(时间限制:7 分钟) 24 3 1 答案:星期一 4、 瓶中取酒: 有 1 个葡萄酒...

  • Java拿火柴游戏实训报告

    2011.12.31 一、 程序功能介绍火柴游戏的功能时通过用户与计算机相互对拿火柴的...(MAX_TAKE + 1);//将面板中的火柴的数量对4取余之后赋给电脑 要拿的火柴...

  • 火柴游戏

    火柴游戏_生活休闲。不同的火柴杆游戏各有特点,当你玩 一个新的类型时,第一个题目很重要,如 果经过自己的思考,能独立完成游戏,那 下面的题目就会更容易了。开...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email