小白鼠检测毒药问题

面试经典 Finley Fu 2019-11-01 2评论 380
有1000个一模一样的瓶子,其中有999瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有10只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?

这个问题我们可以用二进制来进行解答。

2^9 = 512   

2^10 = 1024  

因此10个小白鼠即可。

为了便于理解,我们先设定 n=3,给每只小白鼠进行编号:a1、a2、a3,给药水进行编号0、1...n-1

因此我们得到下表:

a1 a2 a3 药水
0 0 0 0
0 0 1 1
0 1
0 2
0 1 1 3
1 0 0 4
1 0 1 5
1 1 0 6
1 1 1 7

根据图表下面1的位置,我们让a1小白鼠喝4、5、6、7号药水,a2小白鼠:2、3、6、7,a3小白鼠:1、3、5、7

然后我们就静待时间到后小白鼠的死亡情况,0代表存活,1代表死亡,根据a1、a2、a3的顺序组成二进制数字,最后得到的十进制数字就是有毒药水编号。

例如:最后情况为 a1死亡,a2死亡,a3存活,那么对应的二进制为110,十进制为6,则6号药水有毒。