【智力面试题】三人三鬼过河苦逼的码农关注共 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鬼鬼复盘如果在面试的时候遇到这道题,不要一开始就凭着直觉往前冲,那样就是着了圈套,容易陷进去。更聪明的做法,是想明白这是个多分支情况,然后用多叉树来辅助思考,同时在脑海里构思出递归的逻辑。用程序的思维解决场景问题,这就是三人三鬼的意义所在。 浏览 125点赞 评论 收藏 分享 手机扫一扫分享分享 举报 评论图片表情视频评价全部评论推荐 经典智力面试题:一家人过桥Java技术迷0阿里、华为三道面试题!Java研发军团0三道链表经典面试题C语言题库0Gbrainy智力游戏gbrainy是一个为GNOME设计的智力游戏,属于教育软件,旨在激发大脑潜力,授权协议是GNUGPL。使用C#编写,基于Mono并移植到Sugar图形环境以及MicrosoftWindows。主要包Gbrainy智力游戏gbrainy是一个为GNOME设计的智力游戏,属于教育软件,旨在激发大脑潜力,授权协议是GNU G中国卖家过河,亚马逊“拆桥”亿欧网0三歪推荐:Redis常见的面试题Java3y0【收藏分享】2022年PHP中高级面试题(三)码农编程进阶笔记0【金三银四】Redis面试题(2021最新版)麒麟改bug0三年前,我做错的那道面试题think1230点赞 评论 收藏 分享 手机扫一扫分享分享 举报