【智力面试题】三人三鬼过河

苦逼的码农

共 1719字,需浏览 4分钟

 ·

2021-07-13 18:36

这段时间牛牛每天搬砖干饭,盼星星盼月亮终于又盼到了令人激动的周五!今天给大家分享一道有趣的算法题,周末就可以安心躺尸一下下了。

01
故事起源
三个人三只鬼结伴郊游,经过一条河,河上只有一艘小木船,木船只有两个位置,每次只能载2个人或鬼,河两岸人的数量如果小于鬼的数量,人就会被鬼无情的吃掉。问怎样过河人才能安然无恙?



02
问题剖析
我们先来提取几个关键信息:

第一,船只有两个位置,翻译过来就是每次乘坐的情况只能是一人一鬼、两人、两鬼这三种

第二,船开到对岸要回来,需要有人或鬼驾驶,船自己肯定不会回来,这是个隐藏信息

第三,也是最明显的一个,任何时候船两边人的数目,必须要大于等于鬼。

我们的策略,必须基于这三个要点开始。

好了,小伙伴们一定已经跃跃欲试了吧。

Let's Go!

03
花式过河


第一轮

河的这边有三人三鬼,对岸无人,因为一来一回,其实每次送过去的只有一个。

因为目前河这边是人鬼等量,所以必须保证送一只鬼过去,另一个开船的无论是鬼还是人,结果都一样。人或鬼划船回来,剩下一只鬼在对岸,就进入了(3人2鬼-0人1鬼)状态。


第二轮

这一轮给对面送人,还是送鬼呢?我们其实每一轮都有五种过河选择,一人、一鬼、一人一鬼、两人、两鬼。我们就按这个顺序来想想:

1.一个人划船去对岸,得回来一个,如果是第一轮留下的鬼回来,那河这边的人就凉了(2人3鬼-1人0鬼),所以必须是人原路返回,那这样就没有意义了。

2.一只鬼去到对岸,不自己原路返回的话,只能带上之前的鬼一起,这样就回到了起点(3人3鬼-0人0鬼),也没有什么意义。

3.一人一鬼去对岸,则对岸人会遭到鬼毒杀(2人1鬼-1人2鬼),哒咩❌!

4.如果是两人一起过河,那河这边留下的那个兄弟,就会惨遭毒手

5.两鬼去对岸,得回来一个,进入(3人1鬼-0人2鬼)状态。

所以看起来我们选择好像挺多,其实只有一条路可走:两鬼过去,得回来一个,进入(3人1鬼-0人2鬼)状态。


第三轮

这一轮,我们还是按我们的5条路走走看:

1.一个人划船去对岸,卒。

2.和第二轮一样,一只鬼过去,不自己原路返回的话,只能两只鬼一起回来,这样就回到了我们第一轮结束的状态,没有实质意义。

3.一人一鬼过去,那过去对岸的人就凉了。

4.两鬼到对岸,这一轮河这边的鬼只剩一只,鬼不够用啊~

5.两人到对岸,此时(1人1鬼-2人2鬼),得把船划回来,因为此时是平衡状态,如果不原样返回的话,只能是一人一鬼回来,进入(2人2鬼-1人1鬼)状态。


第四轮

这种情况下,其实选择已经比较明显了,不过我们还是按之前的思路来看:

1.一个人划船过去,那留在河这边的小伙伴就凉凉了。

2.一只鬼过去,那么对岸的小伙伴就凉了。

3.一人一鬼过去,此时(1人1人-2人2鬼),在第三轮第五点已经出现过了,是个死循环。

4.两鬼到对岸,岸的小伙伴又凉了

5.两人去对岸,此时(0人2鬼-3人1鬼),此时只能让一只鬼独自撑船回去。那么就是(0人3鬼-3人0鬼)的局面了。


第五轮

现在一看,稳了啊!两只鬼划船到对岸,再回去一只(0人2鬼-3人1鬼),最后两只鬼一起过河。

三人三鬼,都成功过河,且没有发生任何流血事件,画面非常和谐!


04
思路整理
可以看到,我们在思考过程中,其实是根据可能的情况,按直觉先一条路走到底。如果发现打了一圈,回到之前的状况,或者直接就是条死路,就另辟蹊径。

其实,这种演绎过程就是搜索的逻辑。三人三鬼,我们还可以凭借记忆,回到之前的状态,要是五人五鬼,就很难凭记忆回溯了。

更为清晰的路径,是从一开始,就画一颗树,这棵树会指引我们正确的方向!

按照可能的情况一步一步往下走


05
鬼鬼复盘


如果在面试的时候遇到这道题,不要一开始就凭着直觉往前冲,那样就是着了圈套,容易陷进去。

更聪明的做法,是想明白这是个多分支情况,然后用多叉树来辅助思考,同时在脑海里构思出递归的逻辑。

用程序的思维解决场景问题,这就是三人三鬼的意义所在。



浏览 123
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报