写点什么

「腾讯面试题」兔子试毒

发布于: 2021 年 06 月 30 日
「腾讯面试题」兔子试毒

今天给大家分享一道有趣有料的算法题,希望能让大家开启一天的好心情。


01

故事起源

有 1000 瓶药水,其中有一瓶是毒药,只要喝上一滴,一天之后就必死无疑。


现在提供一批兔子来试毒,那我们怎么花最少的兔子、最少的时间,找出这瓶毒药呢?


02

条件分析


喝一滴就死掉,换句话说,那一瓶药水是可以给多只兔子喝的。要花最少的兔子,又要花最少的时间,看起来像是时间与空间的决策,不如我们先来简化问题:

1.只追求时间,最快速度找出药水。

2.只追求空间,节约兔子,时间可以慢慢来。

这样从简单角度辅助思考一下,也能为我们深入思考打下基础。

03

花式试毒


追求时间

简单来说,就是堆兔子。直接拿 1000 只兔子试毒,一只兔子负责一瓶药水。结果自然是耗用 1000 只兔子,1 天出结果。这样的优势比较明显,就是快;缺点也明显:使用的兔子太多,占资源,不环保。


追求空间

如果我们出于环保考虑,节约兔子,那么可以考虑用 2 分。第一轮就分为 500 瓶毒药为一组,先放一只兔子,每瓶药水喝一滴,这样可以排除 500 瓶。如果活着,就继续用这只兔子,如果死了,就补充兔子。我们按最坏情况来算:每次都要消耗掉一只兔子。


下一轮 250 瓶,这样循环迭代,1000->500->250->125->63->32->16->8->4->2->1;

10 个箭头,就是 10 次,也就是用了 10 天。这样我们只用了 10 只兔子,很节约,不过就是等得太心慌。


中庸之道

把前两种方式综合一下,我们可以不用 1000 只兔子,也可以不用等足足 10 天。

把 2 分,变成多分。比如,9 只兔子的话,每次能分 10 份,每轮补充兔子到 9 只,这样试完 1000 瓶药水,只需要 3 天,1000->100->10->1。

2 只兔子的话,就是 3 份,1000->333->111->37->(12,12,13)->(4,4,5)->(2,2,1) -> 1;

规律也很明显,天数为 d,分 a 份,则兔子是 a-1 只,药水 N 瓶,那么 d 等于以 a 为底 N 的对数(logaN)。比如,当耗用 2 只兔子时,a 为 3,算出来正好是 7 天,和我们刚才的推算是一样的。

计算机思维

还有没有更好的办法呢?时间短,效率高。

当然有,因为一次可以喝多瓶药水,那么我们可以用 10 只兔子,模拟出 1024 种情况。

给药水编号,从 1-1000,兔子也编上号,1-10 号,1000 瓶药水编号,都转换为二进制编号,1 就是 000 000 0001,1000 就是 111 110 1000。


这种情况下,第几位为 1,就让对应的兔子喝一滴药水。由于编号都是独一无二的,所以最后根据死掉的兔子,反过来组合一下,就是药水的编号。


如此一来,10 只兔子,只花 1 天,就能试毒成功。无论空间,还是时间,都是最快的。

04

兔兔复盘

如果你是使用 1000 只兔子试毒,那么说明你对时间很敏感;如果是二分法,那你一定是个节约成本的大师;如果使用多分法,说明你懂得在空间和时间上,取一个均衡,深谙中庸之道;如果你能很快想到二进制模拟,那么你一定是对计算机 01 存储非常熟悉!

是选择时间?或空间?或寻求平衡?亦或是有办法另辟蹊径,两者兼备?相信随着思维的循序渐进,你会有所感悟。

今天分享的这道题不光有趣,还是大厂热门面试题,看起来似乎很简单,但其实是有巧思在其中的,它考察了你的思维方式和逻辑能力,希望大家在阅读过程中有所收获!

用户头像

还未添加个人签名 2020.09.07 加入

还未添加个人简介

评论

发布
暂无评论
「腾讯面试题」兔子试毒