微软研究院有多难进 [微软面试中的过桥问题]

  这是世界著名的微软公司招聘人才时的两道面试题。其中蕴含的统筹优化的数学思想方法,应该引起我们的关注和重视。因为培养自身在生产生活实际中寻求合理方案和最优解答的能力,是现代人至关重要的必备素质。
  【过桥问题1】小明一家过一座桥,过桥时是黑夜,所以必须有灯。现在小明过桥要1秒, 小明的弟弟要3秒,小明的爸爸要6秒,小明的妈妈要8秒,小明的爷爷要12秒。每 次此桥最多可过两人,而过桥的速度依过桥最慢者而定,而且灯在点燃后30秒就会熄灭。问:小明一家如何过桥?
   【分析】首先必须明确的是,要节省时间,根据“每次此桥最多可过两人”的条件限制,可以确定每次是两人一起过桥。
  其次因为有人必须返回照明,所以我们接着可以判断的是,最好是让用时最少的小明担任返回任务,如果难以实现,那也应该让用时较少的弟弟担任返回任务。
  再就是为了尽可能节省时间,我们应该让用时较多的人一起过桥,这样不至于让这些人分散多增加耗时。比如小明的妈妈和爷爷一起过桥只用时12秒,而如果分开两次过桥的话,用时8+12=20秒就会大大增加。
  有了这样前提判断,那么接下来我们就不难得到以下优化配置:
  (1)小明、弟弟过桥,用时3秒,紧接着小明持灯返回1秒;
  (2)爷爷、妈妈过桥,用时12秒,紧接着弟弟持灯返回3秒;
  (3)小明、爸爸过桥,用时6秒;紧接着小明持灯返回1秒;
  (4)小明、弟弟过桥,用时3秒,一家五人汇合;
  一家过桥总用时为3+1+12+
  3+6+1+3=29秒,刚好在灯燃尽的范围内。
  【过桥问题2】 U2合唱团的4名成员伯纳、艾吉、埃达姆、劳瑞赶往演唱会现场,他们在途中必须跨过一座桥。4个人到达桥的一端,准备过桥时,天已经黑了。他们只有一只手电筒,一次最多可以有两人一起过桥,而且过桥的时候必须持有手电筒,所以,就得有人把手电筒带来带去,来回桥的两端。注意:手电筒是不能用扔的方式来传递的。4个人的步行速度各不同,若两人同行,则以较慢者的速度为准。伯纳需花1分钟过桥;艾吉需花2分钟过桥;埃达姆需花5分钟过桥;劳瑞需花10分钟过桥。请问:他们能在17分钟内过桥吗?
  【分析】 由题意可知,每次最多可以有两人一起过桥,而且过桥的时候必须持有手电筒,所以,每次要有一人回去送手电筒,直到4个人全部过桥。因此他们过桥的情形只能是:2人去→1人回→2人去→1人回→2人去。也就是说,过桥的总时间是由五段来回的时间组成,这是一个首要的判断。
  有了这个判断,下面就是列举出所有可能的方案,进行试验筛选。从大的方面来说,一种是让花时间较多的两人先过桥,一种是让花时间较少的两人先过桥。先来考察让花时间较多的两人先过桥的情况:
  若让埃达姆(5分钟)和劳瑞(10分钟)先过桥,他们去时用10分钟,埃达姆回去送手电筒用5分钟;然后,艾吉(2分钟)和埃达姆(5分钟)一起过桥,去时用5分钟,此时已用去20分钟,而且只有3人过了桥,显然这种方案不可取。
  既然如此,我们再来考察让花时间较少的两人先过桥的情况:
  如果让伯纳(1分钟)和艾吉(2分钟)先过桥,他们去时用2分钟,伯纳回去送手电筒用1分钟;然后,埃达姆(5分钟)和劳瑞(10分钟)一起过桥,去时用10分钟。这时,已过桥的有3人,艾吉(2分钟)、埃达姆(5分钟)和劳瑞(10分钟),还剩下伯纳(1分钟)没过桥。显然,应该由艾吉回去接伯纳,来回共需2×2=4(分)。这样,4人过桥共用时: 2+l+10+2+2=17(分),满足要求。
  在这两道难度各异本质相同的面试题解答中,我们不难看出统筹规划的缩影。它反映出人类实践活动中普遍的最优化概念,即要在尽可能节省人力、物力和时间前提下,争取获得在可能范围内的最佳效果。

推荐访问:过桥 微软 面试