标题: [转贴]有趣的小题目~天使与魔鬼 [打印本页]
作者:
武骧金星 时间: 2007-5-7 22:32 标题: [转贴]有趣的小题目~天使与魔鬼
在一个无限大的国际象棋棋盘里有一个天使和一个魔鬼。
游戏规则如下：
１，天使每回合可以向上、下、左、右四个方向中任一方向走最多Ｎ格（Ｎ为自然数）且天使不可以不走
２，魔鬼每回合可以在棋盘中除天使当前所在位置的任何一格步下陷阱。陷阱是永远存在的且陷阱是可见的且不能越过陷阱
３，天使与魔鬼都是完全理性的～（这个好象是废话）
请问：天使永远不会被魔鬼抓住所需Ｎ的最小值是多少？
[ 本帖最后由 武骧金星 于 2007-5-19 22:08 编辑 ]
作者:
武骧金星 时间: 2007-5-7 22:33
顺便说下：我是不知道答案的～所以～各位请洒潘江，各倾陆海云尔～
作者:
KYOKO 时间: 2007-5-8 12:01
不清楚,但既然是任意一格都可能有陷阱
感觉不存在这样的N
作者:
武骧金星 时间: 2007-5-8 12:13
~棋盘是无限大的~
作者:
KYOKO 时间: 2007-5-8 12:55
无限大怎样?
对于任一格都可能有陷阱,无限大同有限大没什么区别
作者:
wfldbdlc 时间: 2007-5-8 22:19
个人觉得题目不是很严谨。
应该加上天使行进的路线上如果有陷阱则不能跃过。
感觉N>1就行。
作者:
夜雨落枫 时间: 2007-5-8 22:27
原帖由 KYOKO 于 2007-5-8 12:01 发表
不清楚,但既然是任意一格都可能有陷阱
感觉不存在这样的N
２，魔鬼每回合可以在棋盘中的任何一格步下陷阱。陷阱是永远存在的且陷阱是可见的~
每回合啊，不可能每一格都有陷阱的
感觉必须加一个条件：有陷阱就不能越过
作者:
武骧金星 时间: 2007-5-8 22:36
是不能越过陷阱
[ 本帖最后由 武骧金星 于 2007-5-8 22:41 编辑 ]
作者:
武骧金星 时间: 2007-5-8 22:39
看来我不能随意修饰题目~大汗
作者:
武骧金星 时间: 2007-5-8 22:40
我哭了，我犯了个极其严重的错误
作者:
KYOKO 时间: 2007-5-9 00:21
原帖由 夜雨落枫 于 2007-5-8 22:27 发表
２，魔鬼每回合可以在棋盘中的任何一格步下陷阱。陷阱是永远存在的且陷阱是可见的~
每回合啊，不可能每一格都有陷阱的
感觉必须加一个条件：有陷阱就不能越过
没看清我说的吗?
"每一格都有陷阱"同"每一格都可能有陷阱"意义完全不一样
作者:
天火 时间: 2007-5-9 22:57
有点围棋的味道，征子，堵眼
慢慢考虑看
作者:
飞龙狂飙 时间: 2007-5-10 21:42
不懂得。
作者:
墨叶 时间: 2007-5-11 10:39
我估计3步就够了.
已证2步不行.
目前在证明3步中.
作者:
葉洛幻靈 时间: 2007-5-12 20:33
根据围棋的一个理论 忘了哪个了~~~
似乎只要1格 就永远抓不到的~~~
因为无限大~~~所以没有角落~~~
[ 本帖最后由 葉洛幻靈 于 2007-5-12 20:49 编辑 ]
作者:
墨叶 时间: 2007-5-13 18:56
两步可以抓住,因为不能越过陷阱.
证明我会想写出来供大家参考.
作者:
墨叶 时间: 2007-5-18 18:50
天使只走两步可以抓住.
以天使所在起点为原点建立直角坐标系.
当天使移动到(X,Y)时.
一,若X=0(或Y=0),则在(0,Y+2|Y|/Y)[或(X+2|X|/X,0)]放置陷阱.
二若X,Y均不为零,判断B(X,Y+2|Y|/Y),C(X+2|X|/X,Y)是否存在陷阱.
1'若B,C均无陷阱,则在(X+2|X|/X,Y+2|Y|/Y)放置陷阱;
2'若B,C有一处有陷阱,则另一处放置陷阱.
作者:
武骧金星 时间: 2007-5-18 21:53
完全看不懂~能否解释一下~大汗~
作者:
墨叶 时间: 2007-5-18 23:39
当天使移动到(X,Y)时.
一,若X=0(或Y=0),则在(0,Y+2|Y|/Y)[或(X+2|X|/X,0)]放置陷阱.
二若X,Y均不为零,(为便与讨论,假设在第一象限,既X>0,Y>0).
判断B(X,Y+2),C(X+2,Y)是否存在陷阱.
1'若B,C均无陷阱,则在(X+2,Y+2)放置陷阱;
2'若B,C有一处有陷阱(设为
,则另一处(即C)放置陷阱.
以上两种情况都可以限制天使的远离原点.
你可以实际操作下,就可以明白了.
只是这种方法只对天使移动2步可以分析.
作者:
武骧金星 时间: 2007-5-19 17:52
总算有点明白了~
那么N=3的情况如何?
作者:
武骧金星 时间: 2007-5-19 22:07
传说中的公瑾大人出现了~
哇哇哇~难道我又要编辑题目吗~
作者:
墨叶 时间: 2007-5-20 00:27
原帖由 武骧金星 于 2007-5-19 22:07 发表
传说中的公瑾大人出现了~
哇哇哇~难道我又要编辑题目吗~
他是说我的解法有问题.
原帖由 周瑜 于 2007-5-19 21:44 发表
2步似乎仍有问题，若天使位于(X,Y)时，将陷阱设置在(X+2,Y+2)，那么天使移动到(X,Y+1)，这时怎么设置陷阱。
陷阱放在(X+2,Y+3)处.
能堵死右上角的路.
作者:
fy945 时间: 2007-5-22 11:43
的确n=2会被抓。
23楼的情况，无法再向上移动，因为必然会导致移动后的右侧有陷阱，那么在上方+2处设置陷阱，就无法向上跳2格，也无法向右跳2格，顶多能跳1格，必然被抓。
作者:
[3]Alonely 时间: 2007-5-23 15:54
我觉得N=2不会有问题啊,由于棋盘是无限大的,不会出现如墨叶所说的“2'若B,C有一处有陷阱(设为,则另一处(即C)放置陷阱”的情况出现。
如果以开始天使在（0，0）点，那么，魔鬼若在（2，0）点布置陷阱，我只要移动到（0，2）点，那么按照墨叶的方法，在（2，4）点布置陷阱，再移到（0，4）点，如此可以沿Y轴一直走下去。
我觉得N=1应该都是可以的，大家多讨论。
作者:
墨叶 时间: 2007-5-24 10:06
请楼上的看清楚17楼的回复.
如果
移动到（0，2）点,会在(0,4)放置陷阱.
作者:
[3]Alonely 时间: 2007-5-24 15:37
原帖由 墨叶 于 2007-5-24 10:06 发表
请楼上的看清楚17楼的回复.
如果
移动到（0，2）点,会在(0,4)放置陷阱.
对不起,看错了,的确是不行的
作者:
豪杰 时间: 2007-5-27 11:15
这个跟围棋有一点点关系，但又不同，N>？
作者:
秋旭 时间: 2007-6-6 11:48
N为无限
因为天使和魔鬼的智商是一样的。
而且棋盘无限大，那么假如天使一直向上走，直到遇到障碍为止。
又因为天使一次可以走N步，魔鬼一次只能放一个陷阱。
所以，陷阱数=天使行动的次数≠天使的行动格数。
作者:
nonsensor 时间: 2007-6-7 08:49
以前学LOGIC PROGRAMMING的时候做过这道题
“天使与魔鬼都是完全理性的”
最优往往都是很简单的。
作者:
茅延安 时间: 2007-12-17 21:03
我不了解顶楼题目编辑的历史。不过，如果按现在这个题目来考虑，n=2时应该抓不住。
看到墨叶的意见，研究了一下，发现其算法有一些问题。
1.无限大的棋盘，无论天使在哪，都相当于魔鬼先走棋。你可以把魔鬼第一次走棋之前的天使所在位置设为原点（当然也可以不必如此）。这样之后的“分情况讨论”（判断x、y是否为0甚至所在象限）就意义不大了，因为那根本就是同一种情况。而对同一种情况的不同处理方式也体现了算法的漏洞，这在一些关键步骤时会表现为处理对策的不明确。
2.通过在左上、左下、右上、右下四个方向设置陷阱限制天使向外圈逃逸，这个策略没有问题。但算法不能在有穷步内完成。天使最简单的对策就是单步和双步结合，可以轻松突破任何一层斜向防御。
举个最简单的例子，假设天使现在位于(0,0),魔鬼已经控制了(2,0)(-2,0)(0,2)(0,-2)(2,2)(-2,-2)(-2,2)(2,-2)八个陷阱
此时天使(1,0)
魔鬼可以封堵上面或下面，假设(1,1)
天使(1,-1)
此时十字路口已经畅通，无论魔鬼怎样封堵天使都可以逃逸。
天使向外逃窜的过程就是刚才那一步骤的不断重复。
而实际上，在围捕天使的过程中连上面的局面都几乎不可能形成，更遑论抓住天使了。
作者:
stormzhou3721 时间: 2007-12-29 23:20
天使在行进的路上有陷阱，只有一直往斜向走即可以永远碰不到（为无限大的棋盘），则N>=1.
作者:
huyou75 时间: 2007-12-30 11:17 标题: 回复 #30 茅延安 的帖子
我认为阁下没有弄清楚题意,N的最小值既是说N必须是一个定值,既是说每一步走的数目一定,这样此题才有意义,否则即可用单双步交替的方法,即可保证天使永远不被抓住.(小子愚见,若有不对之处,请多包含)
作者:
茅延安 时间: 2007-12-30 18:43
原帖由 huyou75 于 2007-12-30 11:17 发表
我认为阁下没有弄清楚题意,N的最小值既是说N必须是一个定值,既是说每一步走的数目一定,这样此题才有意义,否则即可用单双步交替的方法,即可保证天使永远不被抓住.(小子愚见,若有不对之处,请多包含)
１，天使每回合可以向上、下、左、右四个方向中任一方向走最多Ｎ格（Ｎ为自然数）且天使不可以不走
回樓上的朋友：如果每回合都必須走N格，既不能多又不能少，那么原題目的“最多”兩個字就沒有任何意義了
而且，如果題意真的如你所說，那么N=一切自然數。都是把N=1的情況“放大”了。
作者:
佐裹义师 时间: 2008-2-15 13:11
我还是看答案不一看数学就头痛
作者:
墨叶 时间: 2008-2-15 13:45
原帖由 茅延安 于 2007-12-17 21:03 发表
我不了解顶楼题目编辑的历史。不过，如果按现在这个题目来考虑，n=2时应该抓不住。
2.通过在左上、左下、右上、右下四个方向设置陷阱限制天使向外圈逃逸，这个策略没有问题。但算法不能在有穷步内完成。天使最简单的对策就是单步和双步结合，可以轻松突破任何一层斜向防御。
举个最简单的例子，假设天使现在位于(0,0),魔鬼已经控制了(2,0)(-2,0)(0,2)(0,-2)(2,2)(-2,-2)(-2,2)(2,-2)八个陷阱
此时天使(1,0)
魔鬼可以封堵上面或下面，假设(1,1)
天使(1,-1)
此时十字路口已经畅通，无论魔鬼怎样封堵天使都可以逃逸。
天使向外逃窜的过程就是刚才那一步骤的不断重复。
而实际上，在围捕天使的过程中连上面的局面都几乎不可能形成，更遑论抓住天使了。
题干改动不大.
我是通过在左上、左下、右上、右下四个方向设置陷阱限制天使向外圈逃逸，
不过是在很远的地方预先设置陷阱,等天使过来.
所以不是控制了(2,0)(-2,0)(0,2)(0,-2)(2,2)(-2,-2)(-2,2)(2,-2)八个陷阱,
而可以更远的,以逸待劳.
如果你有围棋棋盘,我们可以在网上交流下,可能有新的想法.
| 欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |