[转贴]有趣的小题目~天使与魔鬼

在一个无限大的国际象棋棋盘里有一个天使和一个魔鬼。

游戏规则如下：

１，天使每回合可以向上、下、左、右四个方向中任一方向走最多Ｎ格（Ｎ为自然数）且天使不可以不走
２，魔鬼每回合可以在棋盘中除天使当前所在位置的任何一格步下陷阱。陷阱是永远存在的且陷阱是可见的且不能越过陷阱
３，天使与魔鬼都是完全理性的～（这个好象是废话）

请问：天使永远不会被魔鬼抓住所需Ｎ的最小值是多少？

[[i] 本帖最后由 武骧金星 于 2007-5-19 22:08 编辑 [/i]]

顺便说下：我是不知道答案的～所以～各位请洒潘江，各倾陆海云尔～

不清楚,但既然是任意一格都可能有陷阱
感觉不存在这样的N

~棋盘是无限大的~

无限大怎样?

对于任一格都可能有陷阱,无限大同有限大没什么区别

个人觉得题目不是很严谨。
应该加上天使行进的路线上如果有陷阱则不能跃过。

感觉N>1就行。

[quote]原帖由 [i]KYOKO[/i] 于 2007-5-8 12:01 发表
不清楚,但既然是任意一格都可能有陷阱
感觉不存在这样的N [/quote]
２，魔鬼每回合可以在棋盘中的任何一格步下陷阱。陷阱是永远存在的且陷阱是可见的~
每回合啊，不可能每一格都有陷阱的
感觉必须加一个条件：有陷阱就不能越过

是不能越过陷阱

[[i] 本帖最后由 武骧金星 于 2007-5-8 22:41 编辑 [/i]]

看来我不能随意修饰题目~大汗

我哭了，我犯了个极其严重的错误

[quote]原帖由 [i]夜雨落枫[/i] 于 2007-5-8 22:27 发表

２，魔鬼每回合可以在棋盘中的任何一格步下陷阱。陷阱是永远存在的且陷阱是可见的~
每回合啊，不可能每一格都有陷阱的
感觉必须加一个条件：有陷阱就不能越过 [/quote]
没看清我说的吗?

"每一格都有陷阱"同"每一格都可能有陷阱"意义完全不一样

有点围棋的味道，征子，堵眼
慢慢考虑看

不懂得。

我估计3步就够了.
已证2步不行.
目前在证明3步中.

根据围棋的一个理论 忘了哪个了~~~
似乎只要1格 就永远抓不到的~~~
因为无限大~~~所以没有角落~~~

[[i] 本帖最后由 葉洛幻靈 于 2007-5-12 20:49 编辑 [/i]]

两步可以抓住,因为不能越过陷阱.
证明我会想写出来供大家参考.

天使只走两步可以抓住.

以天使所在起点为原点建立直角坐标系.
当天使移动到(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有一处有陷阱,则另一处放置陷阱.

完全看不懂~能否解释一下~大汗~

当天使移动到(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有一处有陷阱(设为B),则另一处(即C)放置陷阱.
     以上两种情况都可以限制天使的远离原点.
    你可以实际操作下,就可以明白了.
只是这种方法只对天使移动2步可以分析.

总算有点明白了~

那么N=3的情况如何?

传说中的公瑾大人出现了~

哇哇哇~难道我又要编辑题目吗~

[quote]原帖由 [i]武骧金星[/i] 于 2007-5-19 22:07 发表
传说中的公瑾大人出现了~

哇哇哇~难道我又要编辑题目吗~ [/quote]

他是说我的解法有问题.


[quote]原帖由 [i]周瑜[/i] 于 2007-5-19 21:44 发表
2步似乎仍有问题，若天使位于(X,Y)时，将陷阱设置在(X+2,Y+2)，那么天使移动到(X,Y+1)，这时怎么设置陷阱。 [/quote]

陷阱放在(X+2,Y+3)处.
能堵死右上角的路.

的确n=2会被抓。

23楼的情况，无法再向上移动，因为必然会导致移动后的右侧有陷阱，那么在上方+2处设置陷阱，就无法向上跳2格，也无法向右跳2格，顶多能跳1格，必然被抓。

我觉得N=2不会有问题啊,由于棋盘是无限大的,不会出现如墨叶所说的“2'若B,C有一处有陷阱(设为,则另一处(即C)放置陷阱”的情况出现。
如果以开始天使在（0，0）点，那么，魔鬼若在（2，0）点布置陷阱，我只要移动到（0，2）点，那么按照墨叶的方法，在（2，4）点布置陷阱，再移到（0，4）点，如此可以沿Y轴一直走下去。
我觉得N=1应该都是可以的，大家多讨论。

请楼上的看清楚17楼的回复.
如果  
  移动到（0，2）点,会在(0,4)放置陷阱.

[quote]原帖由 [i]墨叶[/i] 于 2007-5-24 10:06 发表
请楼上的看清楚17楼的回复.
如果  
  移动到（0，2）点,会在(0,4)放置陷阱. [/quote]
对不起,看错了,的确是不行的

这个跟围棋有一点点关系，但又不同，N>？

N为无限
因为天使和魔鬼的智商是一样的。
而且棋盘无限大，那么假如天使一直向上走，直到遇到障碍为止。
又因为天使一次可以走N步，魔鬼一次只能放一个陷阱。
所以，陷阱数=天使行动的次数≠天使的行动格数。

以前学LOGIC PROGRAMMING的时候做过这道题
“天使与魔鬼都是完全理性的”
最优往往都是很简单的。

我不了解顶楼题目编辑的历史。不过，如果按现在这个题目来考虑，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)
此时十字路口已经畅通，无论魔鬼怎样封堵天使都可以逃逸。
天使向外逃窜的过程就是刚才那一步骤的不断重复。
而实际上，在围捕天使的过程中连上面的局面都几乎不可能形成，更遑论抓住天使了。

天使在行进的路上有陷阱，只有一直往斜向走即可以永远碰不到（为无限大的棋盘），则N>=1.

回复 #30 茅延安 的帖子

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

[quote]原帖由 [i]huyou75[/i] 于 2007-12-30 11:17 发表
我认为阁下没有弄清楚题意,N的最小值既是说N必须是一个定值,既是说每一步走的数目一定,这样此题才有意义,否则即可用单双步交替的方法,即可保证天使永远不被抓住.(小子愚见,若有不对之处,请多包含) [/quote]
[quote]１，天使每回合可以向上、下、左、右四个方向中任一方向走[color=Sienna]最多[/color]Ｎ格（Ｎ为自然数）且天使不可以不走[/quote]
回樓上的朋友：如果每回合都必須走N格，既不能多又不能少，那么原題目的“最多”兩個字就沒有任何意義了

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

我还是看答案不一看数学就头痛:qoo+

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

[/quote]

题干改动不大.

我是通过在左上、左下、右上、右下四个方向设置陷阱限制天使向外圈逃逸，
不过是在很远的地方预先设置陷阱,等天使过来.
所以不是控制了(2,0)(-2,0)(0,2)(0,-2)(2,2)(-2,-2)(-2,2)(2,-2)八个陷阱,
而可以更远的,以逸待劳.

如果你有围棋棋盘,我们可以在网上交流下,可能有新的想法.