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

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

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

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