题目1:有 1000 个一模一样的瓶子,其中有 999 瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有 10 只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?
个人解答:显然需要参考二进制的表示方法,但是腾讯面试当时纠结在时间只有一个星期,而喝下毒药死亡也需要一个星期,似乎只能验证一次。实际上,这个限制正说明我们确实只能利用这10只小白鼠验证一次。于是问题就简单了。将1000瓶水按照二进制编码的顺序给对应的小白鼠喝,比如编号3的水(二进制表示为11)就喂给编号1与编号2小白鼠喝。这样,一星期后看哪几只小白鼠死亡就可以判断哪个编号的水有毒。这个结论成立的前提是只有一瓶毒药,这样只有对应编号的小白鼠才会不幸死亡。
进一步题目:如果你有两个星期的时间,为了从 1000 个瓶子中找出毒药,你最少需要几只老鼠?注意,在第一轮实验中死掉的老鼠,就无法继续参与第二次实验了。
个人解答:有两个星期就可以进行两次实验,每个没死成的小白鼠就能再喝一次,也就是说一个小白鼠可以表示3个状态:第一周死,第二周死,最终也没死。显然就是参考三进制,于是需要3^7 > 1000,即最少7只。方法与之前类似,先给三进制表示为2的位对应的小白鼠喝,再实验三进制表示为1的位对应的小白鼠即可。