【腾讯面试题】兔子试毒

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

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存储非常熟悉！

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

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

END

关注公众号，免费领取学习资料

你好，我是牛牛，普通二本毕业。

本科进腾讯，去过外企，肝过头条。

目前回腾讯担任高级工程师。

想来腾讯的朋友，可以找我内推哦！

点个“赞”和“在看”鼓励一下嘛~