最近面试碰到的一道经典题以及面试官出的的一些follow up (寻找毒药问题)

RT. 原题如下：有1000个瓶，里面有一个毒药，毒药一小时内发作，限定实验时间为一小时，最少需要用几只小白鼠才能找出毒药以及如何测出？
解：需要10只。第n个老鼠喝下第n个bit位为1瓶子中的药水。1小时后，若所有的老鼠都没有发病，那么是第一个瓶子有毒，如果有一些老鼠发病，那么共同喝的那瓶毒药的二进制做与运算，得到的就是共同喝的那瓶，最低位+1，变成整数后，对应的数字即为有毒药水的编号。

Follow up 1:
如果1000瓶里如果有两瓶污染的药水，限定实验时间仍然为一小时，最少需要用几只小白鼠才能找出毒药以及如何测出？

Follow up 2:
如果允许测两轮，或者说时间限制是两小时，那么需要多少只老鼠？

Follow up3：
如果只需要一小时内找出512瓶干净的水，这时候需要几只小白鼠？

这类题知乎上有个回答，总的来说可以从信息熵入手找到一个极限值，之后尝试从工程角度设计方法逼近这个极限，套路其实就那么几种…

458. Poor Pigs?

Follow up 2解析

首先是第一轮死掉的小鼠不能被replace的情况，小鼠有三种状态，第一轮死，第二轮死，和两轮都没死，那么三种状态可以类比为3进制
不能replace:  3^n = 1000
然后是第一轮死掉的小鼠可以被replace的情况，将每2^n瓶混合为1滴做第一轮，选定组别后第二轮确定瓶子编码，量程为2^n * 2^n
能replace：2^n * 2^n = 1000

求思路！给加米

这个好像是绿皮书里的原题

Follow up 1 解析


1000瓶里1瓶毒药的可能性有1000种，1000瓶里有2瓶毒药的可能性有C(1000,2)，即499500种可能。

log2(499500) 为18.93，即需要19只小鼠。

实现方式为两两混合法将1000瓶混合成499500滴（C(1000,2)），并用原题中的方法测得。

同理可得对1000瓶中的N瓶毒药，需要log2(C（1000，N）)只小鼠

Follow up 3解析


还是第n个老鼠喝下第n个bit位为1瓶子中的药水

若找出512瓶干净的水

则确定10个bit位中的第一位为0时有毒还是为1时有毒即可，即需要一只老鼠即可

举例：将第一个bit位为1的药水混合成一滴给老鼠喝，若老鼠死了，则可以确定毒药在第一个bit位为0的瓶子中，那1XXXXXXXXX都是干净的水，有2^9=512瓶

LisaWhite 发表于 2021-08-09 06:04:44
Follow up 3解析

1000瓶水这样做是不是只能筛出来500瓶？

ZYF96 发表于 2021-8-9 14:01
1000瓶水这样做是不是只能筛出来500瓶？

10个老鼠理应是可以筛出2^10 = 1024瓶的