[转贴]有趣的小题目~天使与魔鬼 - 辕门射虎


	茅延安

组别	士兵
级别	忠义校尉
功绩	3
帖子	260
编号	61296
注册	2006-3-2
来自	阿里布达

发表于 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)
此时十字路口已经畅通，无论魔鬼怎样封堵天使都可以逃逸。
天使向外逃窜的过程就是刚才那一步骤的不断重复。
而实际上，在围捕天使的过程中连上面的局面都几乎不可能形成，更遑论抓住天使了。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	茅延安

组别	士兵
级别	忠义校尉
功绩	3
帖子	260
编号	61296
注册	2006-3-2
来自	阿里布达

发表于 2007-12-30 18:43 资料短消息看全部作者

QUOTE:

原帖由 huyou75 于 2007-12-30 11:17 发表
我认为阁下没有弄清楚题意,N的最小值既是说N必须是一个定值,既是说每一步走的数目一定,这样此题才有意义,否则即可用单双步交替的方法,即可保证天使永远不被抓住.(小子愚见,若有不对之处,请多包含)

QUOTE:

１，天使每回合可以向上、下、左、右四个方向中任一方向走最多Ｎ格（Ｎ为自然数）且天使不可以不走

回樓上的朋友：如果每回合都必須走N格，既不能多又不能少，那么原題目的“最多”兩個字就沒有任何意義了

而且，如果題意真的如你所說，那么N=一切自然數。都是把N=1的情況“放大”了。

[广告] 《精忠报国岳飞传完整版》火热发布