面试带领员工坐船过河问题
创始人
2024-12-22 03:31:17
面试带领员工坐船过河问题
标准答案是谁也不过河，要过6个一起过，如果有一个人留下，负责人就不安排过河。是考验负责人的团队精神。
在漆黑的夜里，四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，四个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，四人所需要的时间分别是1、2、5、8分钟；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这四人尽快过桥。
过桥问题详细的描述与解决方案请阅读《过桥问题——经典智力题推而广之五》,共7个小节，作者讲述的非常细致。
结论我给再叙述一下:
以下是构造N个人(N >= 1)过桥最佳方案的方法：
1)如果N=1或者N=2，所有人直接过桥。
2)如果N=3,由最快的人往返一次把其他两人送过河。
3)如果N>=4,设A，B为走的最快的和次快的旅行者，过桥所需时间分别为a,b；而Z,Y为走得最慢的和次慢的旅行者，过桥所需时间分别为z,y。那么
当2b>a+y时，使用模式一将Z和Y移动过桥
当2b
当2b=a+y时，使用模式一或者模式二将Z和Y移动过桥。
这样问题就变成了N-2个旅行者的情形，递归解决即可。
注：这里的模式1指的是A将Z送过桥，然后返回，再把Y送过桥，再返回；模式2指的是A和B先过桥，然后A返回，Y和Z过桥，然后B返回
标准答案是谁也不过河，要过6个一起过，如果有一个人留下，负责人就不安排过河。是考验负责人的团队精神。
在漆黑的夜里，四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，四个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，四人所需要的时间分别是1、2、5、8分钟；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这四人尽快过桥。
过桥问题详细的描述与解决方案请阅读《过桥问题——经典智力题推而广之五》,共7个小节，作者讲述的非常细致。
结论我给再叙述一下:
以下是构造N个人(N >= 1)过桥最佳方案的方法：
1)如果N=1或者N=2，所有人直接过桥。
2)如果N=3,由最快的人往返一次把其他两人送过河。
3)如果N>=4,设A，B为走的最快的和次快的旅行者，过桥所需时间分别为a,b；而Z,Y为走得最慢的和次慢的旅行者，过桥所需时间分别为z,y。那么
当2b>a+y时，使用模式一将Z和Y移动过桥
当2b
当2b=a+y时，使用模式一或者模式二将Z和Y移动过桥。
这样问题就变成了N-2个旅行者的情形，递归解决即可。
注：这里的模式1指的是A将Z送过桥，然后返回，再把Y送过桥，再返回；模式2指的是A和B先过桥，然后A返回，Y和Z过桥，然后B返回
相关内容
热门资讯
蒙牛奶牛工人：AI表格根本不需...
文 ｜ 阑夕 前天，钉钉开了AI钉钉1.1的新品发布会，在一系列的发布和更新里，不出意外的，关于AI...
产学研共舞 中国人寿举办首届A...
【大河财立方 记者 王楠】日前，中国人寿保险股份有限公司（以下简称“中国人寿”，股票代码：60162...
AI能力全面开放 钉钉要让更多...
近日，AI钉钉1.1新品发布暨生态大会在杭州举办，钉钉正式发布全球首个为AI打造的工作智能操作系统—...
周大福珠宝携手AI技术，打造智...
今日，字节火山引擎宣布与周大福珠宝合作，通过AI技术提升珠宝零售行业的运转效率。周大福珠宝构建了统一...