硅谷面试题:有64瓶药,其中63瓶是无毒的,一瓶是有毒的。如果做实验的小白鼠喝了有毒的药,2小时后会死掉,而喝了其他的药,即使同时喝几种都没事。现在只剩下2小时间,请问最少需要多少只小白鼠才能试出哪瓶药有毒?
时间: 2023-05-15 17:04:51 浏览: 358
这是一个经典的二进制搜索问题,最少需要6只小白鼠。将药瓶编号转换为二进制,每只小白鼠喝一位二进制数对应位置上为1的药瓶,如果小白鼠死亡,则说明这瓶药有毒。例如,第一只小白鼠喝1、3、5、7、9、11、13、15号药瓶,第二只小白鼠喝2、3、6、7、10、11、14、15号药瓶,以此类推。这样,最多可以测试2^6=64瓶药,即可确定哪瓶药有毒。
阅读全文