【腾讯面试题】兔子试毒

ゝ一世哀愁。 2022-09-05 00:15 125阅读 0赞

大家好，我是牛牛，经过了忙碌的一周，终于盼来了周五。今天给大家分享一道有趣有料的算法题，希望能让大家开启周末的好心情。

**01**

**故事起源**

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

![520cf732dc26760fca0aa6b7f573bcd1.gif][]

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

**02**

**条件分析**

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

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

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

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

**03**

**花式试毒**

### **追求时间**    ###

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

![532010bc493867b2dba924e4cb4a42d1.png][]

### **追求空间** ###

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

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

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

![b1841367205e0c3eb735369276dd89cd.png][]

###     ###

### **中庸之道**    ###

把前两种方式综合一下，我们可以不用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。

![64d1d288ae10500eb030c0d706a13fdf.png][]

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

![f93bc3540461d0bd1a61620e1a6185d0.png][]

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

**04**

**兔兔复盘**

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

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

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

--------------------

**推荐阅读：**

[专辑|Linux文章汇总][Linux]

[专辑|程序人生][Link 1]

[专辑|C语言][C]

[我的知识小密圈][Link 2]

关注公众号，后台回复「**1024**」获取学习资料网盘链接。

**欢迎点赞，关注，转发，在看，您的每一次鼓励，我都将铭记于心~**

![2406e8079e0c6d8d9e53154fe9c59dce.png][]

嵌入式Linux

微信扫描二维码，关注我的公众号

[520cf732dc26760fca0aa6b7f573bcd1.gif]: /images/20220829/804b17075d2e42a9b777c3c160668545.png
[532010bc493867b2dba924e4cb4a42d1.png]: /images/20220829/6e93c7c465a141539c19a15474903d4e.png
[b1841367205e0c3eb735369276dd89cd.png]: /images/20220829/e15e41fc30814dd6ab4661aa38f119cc.png
[64d1d288ae10500eb030c0d706a13fdf.png]: /images/20220829/c3160e9c74dc4c97a56d7f77a197aecf.png
[f93bc3540461d0bd1a61620e1a6185d0.png]: /images/20220829/286fed45163c496abd6a6325937d42f6.png
[Linux]: https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzA5NTM3MjIxMw%3D%3D&action=getalbum&album_id=1319528681890709506#wechat_redirect
[Link 1]: https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzA5NTM3MjIxMw%3D%3D&action=getalbum&album_id=1351786687592202240#wechat_redirect
[C]: https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzA5NTM3MjIxMw%3D%3D&action=getalbum&album_id=1377857816341577728#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzA5NTM3MjIxMw%3D%3D&chksm=9042f716a7357e003fc6c87cfacb76508df6c06e14fb9f01c54aca3801f456b9ff5b6ce71ef3&idx=2&mid=2247492044&scene=21&sn=695b9297a39bf2d5a4548a161892d182#wechat_redirect
[2406e8079e0c6d8d9e53154fe9c59dce.png]: /images/20220829/e77dc87c9490405d8c7cbadcfbbf901e.png