智商吧 关注:203,471贴子:1,885,348
  • 24回复贴,共1

天使与魔鬼

只看楼主收藏回复

在一个无限大的棋盘上,天使每秒钟可以选择在当前的位置往前后左右移动一步,魔鬼每秒可以在棋盘上挖一个陷阱(不一定连续)。
问:
1. 魔鬼是否一定能够抓到天使?为什么?
2. 假如天使每秒钟可以移动N步,N大于多少之后,魔鬼无法抓住天使?


IP属地:阿联酋1楼2019-09-17 20:40回复
    天使初始0,0;恶魔初始4(intπ+1),0;天使-1,0;恶魔-5,0;


    IP属地:广东来自Android客户端2楼2019-09-17 21:20
    收起回复
      有点像围棋,不过仔细想想,恶魔可以预先远几格下陷阱限制天使的范围,那么一定是能抓到的。换句话说,恶魔可以把无限大的场地变成有限大。具体最少多少步这个算起来有点复杂,下围棋的可能算的快。
      天使移动n步后抓不到呢,只要能超过恶魔下的陷阱坐标就可以永远抓不到吧。
      比如天使初始0,0,恶魔在0,10000先下一手,然后意图先围出10000*10000的场地,天使就得在围出前冲出10000的范围,具体至少n多少,我也不会算


      IP属地:上海3楼2019-09-19 11:45
      收起回复
        这题应当可以列出数学模型吧?
        可惜我不会,哈。
        凭感觉猜,第一题是肯定的,一定能围到。
        第二题才是数学问题的难点。


        IP属地:广东4楼2019-09-19 15:33
        回复
          第一题肯定可以,只要魔鬼斜着预判天使的步就肯定能抓到,用菱形困住.


          IP属地:广西来自Android客户端5楼2019-09-20 11:15
          回复
            1. 可以确保抓到。
            原因其实只有一个:
            天使不能转弯(斜着走),转弯需要花2倍路程,而恶魔挖坑可以转弯(比只走一步的天使快一倍)。
            这就是Euclidean Distance与Manhattan Distance的区别。
            所以天使只能走直线,可以将问题简化成直线上,能不能抓住天使,答案显而易见:可以,2点足矣。


            8楼2019-10-31 09:39
            收起回复
              1. 可以。魔鬼的必胜策略是围一个巨大的框,将天使围住。
              2. 1


              IP属地:北京9楼2023-08-27 19:04
              回复