`

微软过桥问题

阅读更多

U2合唱团在17分钟内得赶到演唱会场,途中必须跨过一座桥,4个人从桥的同一端出发,我们得帮助他们到达另一端,天色很暗,而他们只有一只手电筒。一次同时最多可以有两人一起过桥,而过桥的时候必须持有手电筒,所以就得有人把手电筒带来带去,来回桥两端。手电筒是不能用丢的方式来传递的。4个人的步行速度各不同,若两人同行则以较慢者的速度为准。Bono需花1分钟过桥,Edge需花2分钟过桥,Adam需花5分钟过桥,Larry需花10分钟过桥。他们要如何在17分钟内过桥呢?

这个问题如果用图论来建模(基于系统状态转换模型),就可以以4个人在桥两端的状态来作为节点来构造一个有向图。以已经过桥了的人的状态作为图的节点,初始时没有人过桥,所以以空表示,第一轮有两个人过桥,有6种可能的组合,(1,2)(1,5)(1,10)(2,5)(2,10)(5,10),从空的状态转换到这些状态的需要的时间分别为2,5,10,5,10,10分钟,时间就作为有向边的权值。当有两个人过桥后,需要一个人拿手电筒回去接其他人,这时有四种可能的情况,分别是1,2,5,10中的一人留在了河的对岸,(1,2)这种状态只能转换到(1)(2)两种状态,对应的边的权值分别为2,1分钟,(1,2)转换到(1)时也就是2返回了,返回需要耗时2分钟,依此类推可以建立如图7-6所示的图论模型。

 

 

要求出最少需要多长时间4人全部通过小桥,实际上就是在图中求出(空)节点到(1,2,5,10)节点间的最短路径。根据Dijkstra最短路径算法很容易求出其最短路径:这样总时间为2+1+10+2+2=17分钟。

分享到:
评论

相关推荐

    每日一题:过桥问题1

    其中一个经典案例就是“过桥问题”,这是一个有趣且具有教育意义的逻辑思维题,特别在微软等科技公司的面试中常被提出,用来考察应聘者的问题解决能力。 过桥问题的设定非常简单:有四个人(这里我们假设为A、B、C...

    SOME微软面试题!!

    3. 小明过桥问题:第三个问题是关于小明一家如何过桥的问题,需要考虑过桥的速度和灯的使用。这个问题需要逻辑思维和问题分析。 知识点:逻辑思维、问题分析、时间管理 4. 帽子颜色问题:第四个问题是关于帽子颜色...

    微软公司面试题及答案

    类似过桥问题,最优策略是让最快的人先过桥,然后返回;接着让最慢的两个人一起过桥,由较快的人返回;最后,让剩余的两个人一起过桥。通过这种方式,U2乐队可以在17分钟内安全过桥。 ### 8. 绳子燃烧问题 要使用...

    微软笔试面试题集锦全

    U2合唱团过桥问题** - **解析**:为了解决这个问题,关键在于合理安排成员过桥的顺序,以便最短的时间内完成任务。最佳策略是先让较快的人先过桥,然后让其中一个快的人带着手电筒回来,再让两个较慢的人一起过桥...

    微软智力题和面试题,每个题目都需要你打破思维的常规来回答

    第二个题目,小明一家过桥问题,要求在灯亮的时间内,所有人安全过桥。解题的关键在于合理安排持灯者和过桥组合,使得总时间最短。这里需要的是优化策略和时间管理能力。 猜牌问题,S先生、P先生和Q先生的逻辑推理...

    很好很强大的微软面试题

    **题目3:过桥问题** - **题目描述**:小明一家需要在30秒内通过一座桥,每次只能两人一起过桥,且过桥的速度取决于两人中较慢的一个。每个家庭成员过桥的时间分别为1秒、3秒、6秒、8秒和12秒。 - **解决策略**: ...

    微软面试100题.doc

    15. 过桥问题是一个经典的逻辑谜题,可以通过列出所有可能的过桥组合,并计算时间找到解决方案。 16. 量取4夸脱水的问题,需要通过5夸脱和3夸脱桶的组合操作实现。 17. 保证拿到两颗相同颜色糖的问题,最坏情况下...

    微软笔试试题+很经典啊.docx

    微软公司的招聘方式非常独特,招聘人员会逐项提出所谓的“微软问题”,这些问题或是数学方面的问题,只有一个“正确”答案,或是开放式问题,无论哪种情况,招聘人员至少应该是对你回答问题的方式和对这个问题本身...

    微软面试题目(附答案).pdf

    小明一家过桥问题 **题目描述**:小明一家五口人需要在黑暗中通过一座桥,每次只能过两个人,并且过桥的速度取决于两个人中较慢的一个。过桥所需的时间分别为1秒、3秒、6秒、8秒和12秒。桥上的灯只能亮30秒。如何...

    微软笔试题总结 推理题 计算题

    3. **小明一家过桥问题**:这是一道典型的逻辑优化问题,要求在有限时间内最大化效率。解决办法是让速度最快的人携带灯,每次过桥后返回,以最小化总时间。例如,小明和弟弟先过,小明返回,然后父亲和母亲过,父亲...

    微软面试智力题(附有详细答案)

    微软面试智力题详解 本资源为微软面试智力题,共 46 道题,题目涵盖逻辑推理、数学计算、算法设计等多方面的知识点。以下是对每道题目的详细解释: A. 逻辑推理 2. 将一盒蛋糕切成 8 份,分给 8 个人,但蛋糕盒里...

    微软笔试题

    #### 五、U2乐队过桥问题 **解析:** 这是一道经典的逻辑谜题。目标是在17分钟内让四人全部过桥,同时考虑到不同人的过桥时间,以及每次过桥时必须持有手电筒。 **解答思路:** - 首先让Bono(1分钟)和Edge(2...

    微软笔试面试

    2. **逻辑推理与问题解决**:例如“U2乐队过桥问题”和“遗产分配问题”,这些都是典型的逻辑谜题,需要快速理解问题并找出最有效的解决方案。 3. **逻辑推理与概率**:遗产分配问题实际上涉及到概率和条件判断,...

    微软智力题,题目多种多样~~

    3. 小明一家过桥问题:小明和弟弟先过,1秒,然后小明回去,3秒,小明和妈妈过,8秒,小明回去,1秒,小明和爷爷过,12秒,总共34秒。 4. 帽子问题:3次关灯说明最少3顶黑帽。第一次没人打耳光说明至少有2顶黑帽,...

    微软的100道题--好

    15. **过桥问题**:关键在于优化组合,例如(1,2)过桥,(1)带回,(2,4)过桥,(2)带回,(1,3)过桥,共12分钟。 16. **量水问题**:先用5夸脱桶装满水,倒入3夸脱桶,留下2夸脱,再重复一次,剩余1夸脱,然后将5夸脱桶...

    微软面试100题

    这些题目是微软面试中经常出现的智力和逻辑思维问题,旨在测试候选人的解决问题能力、逻辑推理、数学技能以及对计算机科学基础知识的理解。以下是对部分题目的详细解答: 1. 井盖是圆的因为圆形没有方向性,无论...

    微软面试题(智力题)

    7. U2合唱团过桥问题:Bono和Edge先过,用2分钟,Bono回来,用1分钟,Adam和Larry一起过,用10分钟,Bono和Edge再一起过,用2分钟,共用15分钟,满足条件。 8. 绳子判断半小时:将绳子对折,点燃两端,烧完即为半...

    微软面试智力题.doc

    7、U2合唱团过桥问题,最优解是Bono和Edge先过,2分钟,Bono回带灯,1分钟,Adam和Larry一起过,10分钟,Edge回带灯,2分钟,Bono和Edge再一起过,1分钟,总共18分钟,需要调整方案以满足17分钟内过桥。 8、烧绳子...

    微软面试题及答案(无创造性思维者勿下载)

    3. 小明一家过桥问题:最优解是小明和爷爷先过,然后小明回来带弟弟过去,接着小明和妈妈过去,最后小明再带爸爸过桥,总共需要21秒。 4. 黑帽问题:根据题目描述,第一次没人打耳光说明至少有2顶黑帽,第二次也没...

Global site tag (gtag.js) - Google Analytics