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


	武骧金星

组别	校尉
级别	前将军
功绩	29
帖子	1763
编号	56399
注册	2005-12-31
来自	上海

#1

发表于 2007-5-7 22:32 资料个人空间短消息只看该作者

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

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

游戏规则如下：

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

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

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

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


	武骧金星

组别	校尉
级别	前将军
功绩	29
帖子	1763
编号	56399
注册	2005-12-31
来自	上海

#2

发表于 2007-5-7 22:33 资料个人空间短消息只看该作者

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

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


	KYOKO (★御姐控★)


	唐国公荆南节度使 ★★

组别	节度使
级别	大将军
功绩	1456
帖子	65615
编号	32
注册	2003-8-19
来自	BWL

#3

发表于 2007-5-8 12:01 资料个人空间短消息只看该作者

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

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


	武骧金星

组别	校尉
级别	前将军
功绩	29
帖子	1763
编号	56399
注册	2005-12-31
来自	上海

#4

发表于 2007-5-8 12:13 资料个人空间短消息只看该作者

~棋盘是无限大的~

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


	KYOKO (★御姐控★)


	唐国公荆南节度使 ★★

组别	节度使
级别	大将军
功绩	1456
帖子	65615
编号	32
注册	2003-8-19
来自	BWL

#5

发表于 2007-5-8 12:55 资料个人空间短消息只看该作者

无限大怎样?

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

[广告] 真诚支持说岳，携手共创辉煌


	wfldbdlc

组别	百姓
级别	在野武将
功绩	0
帖子	45
编号	114377
注册	2007-2-28
来自	江西

#6

发表于 2007-5-8 22:19 资料短消息只看该作者

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

感觉N>1就行。

[广告] 真诚支持说岳，携手共创辉煌


	夜雨落枫 (欧阳枫)

组别	校尉
级别	安东将军
好贴	1
功绩	48
帖子	3224
编号	79763
注册	2006-8-20
家族	网络曹操传

#7

发表于 2007-5-8 22:27 资料个人空间短消息只看该作者

QUOTE:

原帖由 KYOKO 于 2007-5-8 12:01 发表
不清楚,但既然是任意一格都可能有陷阱
感觉不存在这样的N

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

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


	武骧金星

组别	校尉
级别	前将军
功绩	29
帖子	1763
编号	56399
注册	2005-12-31
来自	上海

#8

发表于 2007-5-8 22:36 资料个人空间短消息只看该作者

是不能越过陷阱

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

[广告] 真诚支持说岳，携手共创辉煌


	武骧金星

组别	校尉
级别	前将军
功绩	29
帖子	1763
编号	56399
注册	2005-12-31
来自	上海

#9

发表于 2007-5-8 22:39 资料个人空间短消息只看该作者

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

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


	武骧金星

组别	校尉
级别	前将军
功绩	29
帖子	1763
编号	56399
注册	2005-12-31
来自	上海

#10

发表于 2007-5-8 22:40 资料个人空间短消息只看该作者

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

[广告] 真诚支持说岳，携手共创辉煌


	KYOKO (★御姐控★)


	唐国公荆南节度使 ★★

组别	节度使
级别	大将军
功绩	1456
帖子	65615
编号	32
注册	2003-8-19
来自	BWL

#11

发表于 2007-5-9 00:21 资料个人空间短消息只看该作者

QUOTE:

原帖由 夜雨落枫 于 2007-5-8 22:27 发表

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

没看清我说的吗?

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

[广告] 真诚支持说岳，携手共创辉煌


	天火 (天之痕心之伤)

组别	校尉
级别	破虏将军
好贴	2
功绩	33
帖子	760
编号	33672
注册	2005-2-27

#12

发表于 2007-5-9 22:57 资料主页文集短消息只看该作者

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

[广告] 真诚支持说岳，携手共创辉煌


	飞龙狂飙 (捻花微笑)

组别	百姓
级别	在野武将
功绩	0
帖子	46
编号	148958
注册	2007-4-29
家族	轩辕少林寺

#13

发表于 2007-5-10 21:42 资料短消息只看该作者

不懂得。

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


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#14

发表于 2007-5-11 10:39 资料个人空间短消息只看该作者

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

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


	葉洛幻靈

组别	百姓
级别	在野武将
功绩	0
帖子	26
编号	91980
注册	2006-11-18

#15

发表于 2007-5-12 20:33 资料短消息只看该作者

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

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

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


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#16

发表于 2007-5-13 18:56 资料个人空间短消息只看该作者

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

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


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#17

发表于 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有一处有陷阱,则另一处放置陷阱.

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


	武骧金星

组别	校尉
级别	前将军
功绩	29
帖子	1763
编号	56399
注册	2005-12-31
来自	上海

#18

发表于 2007-5-18 21:53 资料个人空间短消息只看该作者

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

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


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#19

发表于 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步可以分析.

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


	武骧金星

组别	校尉
级别	前将军
功绩	29
帖子	1763
编号	56399
注册	2005-12-31
来自	上海

#20

发表于 2007-5-19 17:52 资料个人空间短消息只看该作者

总算有点明白了~

那么N=3的情况如何?

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


	武骧金星

组别	校尉
级别	前将军
功绩	29
帖子	1763
编号	56399
注册	2005-12-31
来自	上海

#21

发表于 2007-5-19 22:07 资料个人空间短消息只看该作者

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

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

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


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#22

发表于 2007-5-20 00:27 资料个人空间短消息只看该作者

QUOTE:

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

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

他是说我的解法有问题.

QUOTE:

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

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

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


	fy945

组别	百姓
级别	奋威校尉
功绩	1
帖子	102
编号	45383
注册	2005-8-12

#23

发表于 2007-5-22 11:43 资料短消息只看该作者

的确n=2会被抓。

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

[广告] 真诚支持说岳，携手共创辉煌


	[3]Alonely (关西一秋)

组别	校尉
级别	后将军
功绩	15
帖子	1526
编号	87051
注册	2006-10-12

#24

发表于 2007-5-23 15:54 资料文集短消息只看该作者

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

[广告] 真诚支持说岳，携手共创辉煌


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#25

发表于 2007-5-24 10:06 资料个人空间短消息只看该作者

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

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


	[3]Alonely (关西一秋)

组别	校尉
级别	后将军
功绩	15
帖子	1526
编号	87051
注册	2006-10-12

#26

发表于 2007-5-24 15:37 资料文集短消息只看该作者

QUOTE:

原帖由墨叶于 2007-5-24 10:06 发表
请楼上的看清楚17楼的回复.
如果
移动到（0，2）点,会在(0,4)放置陷阱.

对不起,看错了,的确是不行的

[广告] 真诚支持说岳，携手共创辉煌


	豪杰


	★

组别	校尉
级别	破虏将军
功绩	17
帖子	743
编号	161113
注册	2007-5-20
家族	轩辕丐帮

#27

发表于 2007-5-27 11:15 资料个人空间短消息只看该作者

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

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


	秋旭

组别	士兵
级别	安国将军
功绩	8
帖子	838
编号	69325
注册	2006-5-21

#28

发表于 2007-6-6 11:48 资料短消息只看该作者

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

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


	nonsensor

组别	校尉
级别	军师将军
功绩	10
帖子	1000
编号	1719
注册	2003-10-28
来自	WZ-XA-SH-SE-...

#29

发表于 2007-6-7 08:49 资料个人空间短消息只看该作者

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

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


	茅延安

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

#30

发表于 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工具条，提高轩辕排名，支持轩辕发展！