这类问题比较多的出现在智力题的范畴中，并且有多个变种，本文对这类题目进行多角度分析，看清问题的本质才是关键。
小白鼠喝药瓶问题
有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
小白鼠的问题比较简单一些，它只有一个时间点来观测结果，所以用空间换时间，空间即表示小白鼠的个数，很明显这里的个数要多一些。
最多是多少？很显然是1000只，每只喝一瓶，但是这个答案显然不是最优的。
所以，我们需要让🐁们将全部的瓶子都尝试才能保证找到答案，漏掉一个瓶子（其实是两个）都不行。
所以很明显一只🐁喝一瓶是不够的，要喝多瓶，极端是每只都喝1000瓶，最后全都死了，结果还是找不到答案，所以不能全喝相同的，要差异化地喝。
分析
首先每个瓶子有独立的编号从0到999，很明显有毒的那一瓶不可能只被一只🐁喝到（因为只有一个机会观测结果，又不能有1000只来做实验），所以需要一瓶被多只喝到。
显然问题的解需要从瓶子的角度来考虑，怎么让一个具体的瓶号（数值）对应多个🐁，并且让🐁尽可能的少呢？
位图法
将十进制转换为二进制，每一个位只能是0和1，对应这里的 喝 和 不喝 两种状态，十进制表示瓶子的数量，二进的位数表示🐁的数量。
所以能涵盖1000的二进制位数是10，2^10=1024>1000，我们需要10只🐁。
比如有毒的是
980序号的瓶子，二进制是11 1101 0100，表示0、1、2、3、5、7位置的🐁都是喝的状态，其余的没有参与。所以这些序号的🐁会死亡，然后根据🐁序号排列后即可得出对应的十进制，也就是瓶子的序号了。
变题
有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。最多用多少🐁来检验出哪个瓶子里有毒药？
这个变题并没有时间的要求，也就是说我们可以「以时间换空间」。
因为🐁测试的结果只有存活与死亡两种结果，所以每次测试可以分为两类，用二分查找的话，二叉树有十层，最坏情况下，给小白鼠喂药的次数为 500+250+125+63+32+16+8+4+2+1=1001。
最坏的情况下，将会使用10个星期才能得到结果，代价呢？
- 最好可能只需要1只就行（每次只喝当前的一半并且没死，下一轮去喝另一半，依次循环，直到只剩一瓶）
- 最坏需要10只（每轮只喝一半，但是每次喝的一半都包括有毒的那一瓶，一直喝到最后一轮只剩的那两瓶）
但它的一个优势是只需要喝1001次药水，即通过10个礼拜的测试，我们节省了「空间」只需要喝1001次。
而位图法相比来说，是一个「以时间换空间」的思路，即虽然在一个星期内就可以得到结果，它的速度快了，但是尝试的次数变多了。
我们以1024瓶来计算，从1到1024这些十进制数中，每个数字用十位长度的二进制表示，每一位都是0和1，并且所有数字的所有位数的0和1的个数是相同的。 总共有1024个十进制数，所以0和1总共的个数为1024个数字*10个bit位=10240个尝试（包括喝和不喝），所以1（即喝）的个数为5120个，也就是说，这种情况下，需要给小白鼠喂药5120 次，约是不限制测试时间的二分方式的喝水次数的5倍。
时间短，那么就需要在单位时间内多做计算（喝水，需要并行计算利用多核），但是获取结论速度快；
时间长，那么就可以减少单位时间的计算次数（量力而行，单核就行啦），但是获取结论速度慢；
如果解决总的问题的复杂度不变，那么解决问题的多个正向因子间的关系是此消彼长的。
小猪喝药水问题
原题来自LeetCode458
There are 1000 buckets, one and only one of them contains poison, the rest are filled with water . They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket contains the poison within one hour.
Answer this question, and write an algorithm for the follow-up general case.
Follow-up:
If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the “poison” bucket within p minutes? There is exact one bucket with poison.
这道题和小白鼠问题的不同之处在于，它有多个时间点来观测结果：在一定的时间范围内（60分钟），通过多轮（15分钟一轮）试验，在样本（水桶数目）一定的条件下， 找到最少的测试标本（🐷）的数目。
这是一个典型的「以时间换空间」的例子，要以最少的测试标本在规定时间内达到找到样本中有毒的那一个。所以它的答案一定比小白鼠的要少。
逆向分析
为了更好的理解这道题，我们可以采用「逆向思维」：从答案入手，反向总结它和参数的关系。
所以我们先从最基本的case分析，即如果我们只有一头🐷，在规定时间条件内（60分钟上限每15分钟得出一轮结果），我们可以让它尝试多少桶水后确立其中的一桶有毒呢？
为了简化理解我们只在0，15，30，45分钟喂水，也假设只在每15min时刻才会死亡，还假设猪猪的肚子容量无限大，将每次喂水的时刻记为第一、二、三、四轮。
一头🐷能在多少桶中找到答案？
很简单，每个时刻喝一桶，最快的情况刚开始就喝到有毒的，然后死掉，确立结果； 最慢的情况是60min时刻还没有死，因为题目说「一定有一桶有毒」，所以就是剩下的那一桶有毒（是的，🐷不一定要死掉^_^）。
所以一头🐷可以在规定时间条件内（60分钟上限每15分钟得出一轮结果），最多可以在 4+1=5 桶中找到一桶有毒（是的，它尽力了，不能再多了。）。
好，让我们再抽象一下。
我们刚才分析了最快和最慢的情况，其实🐷可以在任意一个时刻死去，比如30min时。所以，
对于每头🐷，它应有 5 种状态：15min时死亡、30min时死亡、45min时内死亡、60min时死亡和60min时刻也没有死，即活着。
如果有2头🐷呢？
刚才分析了一头🐷最多可以确立 5 桶中一定有一桶有毒？那么2头🐷是最多能确立 2*5=10 中一桶有毒吗？还能更多吗？
因为🐷在任意时刻可以喝多桶水，假设🐷的肚肚是无限存储的。上述猜测很显然只是在固定时刻喝一桶水，很显然，速度不够快速。 我们没有必要喝完一桶后等待它的效果15min，太浪费时间了。
如果0时刻🐷1喝了n桶，🐷2也喝了n桶，且两边不重复：
- 如果🐷1挂了，那么🐷2只需要在下一时刻开始尝试🐷1上一时刻喝过的那些样本即可，其他的都可以排除，排除的越早喝的越少。
- 如果两头🐷都挂了，可能吗？当然可能。所以二者之间一定有一个交集，保证标本全部死亡时可以直接得到结论，如果有两或两个以上交集可能吗？不可能，因为没有标本再确认哪个样本是有毒的了。
因为两头🐷肯定比一头🐷在样本一定的条件下发现有毒桶的速度要快，所以最坏的case就是某一轮后只剩下一头🐷，要保证它可以在剩余时间的条件下可以对死亡的🐷在上一时刻的样本中继续寻找并得到有毒的样本。
我们在上一节已经分析了，一头🐷时样本最多是 5 桶，所以第一轮后活着的那头在后面的二轮开始时能处理的最大桶数就是 4 ，即退化成了一头🐷的从第二轮开始喝的case。
所以可以得出结论，不要管一头猪一次喝了多少桶水，而是要关注，这轮这头🐷死掉后，剩下的那头🐷可否在剩余时间里测试出死亡的🐷喝过的水中的有毒的水。 并且如果上一轮两头🐷都没有死，那么下一轮这两头🐷一定有一个交集（交点），可以理解为是个二维问题。
所以可以得出，两头🐷的情况下，是一个5^2=25的样本，可以看成一个5*5的二维矩阵，横向是🐷1喝水的顺序，纵向是🐷2喝水的顺序，每一轮都有一个交点，即左上角那一个。
如果🐷1第一轮死亡，则(0,i)是有毒的，且(0,0)无毒，所以🐷2可以从(0,1)到(0,4)开始一共有4个桶，还有三轮（15min开始、30min开始、45min开始），所以一定能找到。
所以看懂了吗？这个逻辑可以抽象为二维矩阵的两个方向，每一头🐷都是均等的朝着各自的「轴向」发展，如果某一轮后一头死掉了，就只剩下一个「轴向」了，变成了一只🐷的case。
如果是3头🐷呢？
很显然直观感觉这个是三维问题而不是简单的二维问题了，三头🐷朝着各自的「轴向」排列的水桶喝下去，想一下魔方的三个轴x、y、z ，🐷彼此仍然是独立的：
- 如果在某一轮后其中一头死了，问题就变成了二维问题，另外两头🐷立刻移动到死亡那头饮用的一个二维横切面（矩阵）表示的桶排列上继续延两个「轴向」分别处理，就像上面的分析一样。
- 如果两头都死了，那么另外一头🐷就只需按照x=n，y=m（因为每一头🐷是相同的问题，所以此时n==m）时的「交线」继续尝试就ok了。
三条平面相交是一个点，两个平面相交是一条线。每一轮三头🐷都没有死亡则下一轮的魔方是一个各个轴向缩小了1个量的更小的魔方，如果最坏的场景会一直喝下去到最后一轮。 然后还都没有死，则最后的那个「核心」位置就是有毒的水桶。
维度和位数
所以到这里这道题的规律我们基本上就搞清楚了，每一头🐷是一个独立维度的问题，n头就是N维，每一个维度包含5个样本（待解决的问题），那么只需要保证5^n大于给定的样本数（这里是1000），取最小的n
为🐷的头数即可。
当维度超过三维时人脑就很难理解，所以这里通过将「维度」和「位数」进行参照即可简化理解，不同的位之间没有关系，彼此按照各自的「轴向」增长变化。
比如，ABC表示一个三个位的变量，每一个位置代表一个维度，每一位都是可以从0变化到9（十进制），所以它能表示的数值最多是 10^3 个，比如：
- 在其他两位不变的情况下（两头🐷同时死亡），某一位可以是0~4，这就表示一条线
- 在其他一位不变的情况下（一头🐷死亡），另外两位可以是0~4，这就表示一个切面
代码实现
懂了上面的逻辑，代码就好写多了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int poorPigs(int buckets, int minutesToDie, int minutesToTest)
{
if (buckets == 1)
return 0;
int base = minutesToTest / minutesToDie + 1;
int r = 1;
for (int i = 1;; i++)
{
r *= base;
if (r >= buckets)
return i;
}
return 0;
}
References
- https://www.zhihu.com/question/19676641
- https://www.zhihu.com/question/60227816
本文首次发布于 LiuShuo’s Blog, 转载请保留原文链接.
