• 2010-09-01

    伞兵的绝密行动 - [IT]

    版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://www.blogbus.com/ma3r-logs/74150065.html

    昨天看到一道算法题,非常有意思——
    空降师某连N个伞兵(绝密军事行动,无特征,如编号、名字)要从高空跳伞,纷纷降落在一个大平原。
    他们会在着陆的瞬间昏厥,并经过合理的时间后醒来。
    他们各自随身带一个仪器,能够在打开的瞬间探测到所有其他队员与自己的相对位置,但只能使用一次。
    为确保他们能够会合,请你设计一个他们跳伞后的行动方案。

    前提与假设

    首先,我们必须假设,当任何一个伞兵探测的时候,所有伞兵都已经着陆。
    或者起码他们能够做到这一点,比如醒后等待足够长的时间。
    如若不然,伞兵们都开始行动了,还不断有人着陆,这个问题就无解了。

    其次,要肯定的是,伞兵们必须知道方向,比如每人有一个指南针。
    否则的话,伞兵怎么能保证走到他想去的地方呢?
    我们知道,在没有任何东西能指示出方向的情况下,一个人是走不出直线的,走出的都是或大或小的圆。
    (如果刚巧有人不知道,去搜一下“鬼打墙”好了。)
    那好,既然大家都知道方向了,到所有人的东南角儿集合好了。
    当然,这不是出题人的本意,那我们只好假设伞兵们不知道方向,但是能走到他们想去的任何位置。

    再次,一个伞兵能够被探测到,说明他身上带着某样东西,可以发射信号。
    那么好办了,所有伞兵都把发射信号的东东扔在原地,自己去重心集合就好了。(跟 grassroots 学的。)
    我知道,这仍不是出题人的本意,那我们只好再假设他们不能丢下任何东东。
    好了,这下出题人应该满意了吧。
    下面,我们分情况讨论。

    只有 1 个人

    那还讨论个屁啊!

    只有 2 个人

    那就直接走过去咯,还怕碰不上?

    所有人都在同一个圆上

    那就沿圆弧儿走过去,走近的一边哦!
    特例,有一个伞兵醒来后可能会发现,所有其他人都在一个点儿上。
    那么是其他人正在通过某一段圆弧儿向自己靠拢,只能原地等着了。
    更特例,恰巧两个伞兵落在一处,所有其他人都在一个点儿上。(感谢 xreborner 提醒。)
    那只要派一个人去找其它人,另一个人在原地等即可。
    如果找到了,领回来;如果没找到,自己回去,其他人正在向他们靠拢。

    如果不巧,两边都一样,那只好随便走一边咯。
    如果更不巧,所有人正好在正 N 边形的 N 个顶点上,而且同时开始行动呢?
    那他们走了一圈儿之后,会发现一个人也没有碰到,那么肯定是最悲剧的事情发生了。
    那么,这时只要他们都往圆心走去就可以聚齐了。

    不是所有人都在同一个圆上

    这时,可以找到一个最小圆,使得所有人都在圆上或圆内(这个最小圆是唯一的)。
    那么,圆上有 2 个人(处于直径位置)或 3 个以上,这些人是参照系,统统不要动,等待别人来接应。
    圆内的人先在圆心聚齐,然后去“收集”圆上的每一个人。
    “收集”的顺序有讲究,可以是大家都到圆上某一个人处,然后就跟“所有人都在同一个圆上”类似了。

    特例,圆上有 2 个人,且所有其他人都位于这条直径的同一侧。
    这时有可能出现一个极端情况——在圆内的人向圆心靠拢的时候,有可能产生“所有人都在同一个圆上”的瞬间。
    如果这时正巧一个伞兵醒来,他的参照系就会和其他人不同。
    为了避免这种状况,在最小外接圆(不是前面提到的最小圆)上的人也不要动,等待别人来接应。
    可以动的人在圆心聚齐后,再到任一个不能动的人处,然后又跟“所有人都在同一个圆上”类似了。

    分享到: