好记性不如铅笔头

数据结构与算法, 编程

【转】限时过桥问题

本文转自:【 http://www.cnblogs.com/anderslly/archive/2011/06/03/2070192.html 】

CONTENTS

趣题一则:如何快速过桥?

问题:

有四个人打算过桥,他们都在桥的某一端,他们的任务是在17分钟内全部到达桥的另一头。当时是晚上,他们只有一只手电筒,最多只能有两人同时过桥,因为伸手不见五指,必须要携带手电筒。必须步行将手电筒带来带去,即扔来扔去是不行的。每个人走路的速度是不同的:甲过桥需要1分钟,乙需要2分钟,丙需要5分钟,丁需要10分钟。两个人一起走的速度等于其中较慢的人的速度。例如,如果第一次让甲和丁一起过桥,当他们到桥的另一端时,已经用了10分钟,如果由丁带回手电筒,那么20分钟就过去了,于是任务失败。那他们到底该怎样过去呢?

解答:

第一次甲和乙同行,然后乙回去送手电筒,用掉4分钟;下一次丙和丁同行,甲回去,用掉11分钟;最后甲和乙再次同行,用掉2分钟。任务完成。

发表评论

7 − 5 =

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据