扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 场景题 > 面试中的智力题 > 3.1000瓶药水里面只有1瓶是有毒的,毒发时间为24个小时,问需要多少只老鼠才能在24小时后试出那瓶有毒

这个问题不太容易想到可以先记住答案,需要老鼠的数量为log_2 1000

为了简化问题,可以先假设有只有8瓶药水,其中有一瓶有毒,根据公式需要 log_2 8=3个老鼠

先将瓶子进行编号为0-7号,用位数表示老鼠,如下图,

将4、5、6、7号药水混合到一起喂给老鼠1,将2,3,6,7号药水混合喂给老鼠2,将1、3、5、7药水混合喂给老鼠3,观察老鼠是否中毒。

中毒的老鼠标号为1,未中毒的老鼠标号为0,将三只老鼠标号组合到一起即为有毒药水的标号。

例如,第老鼠1中毒,老鼠2未中毒,老鼠3中毒。那么三只老鼠的二进制表示为101,即5号药水有毒。因为老鼠1中毒,说明4、5、6、7号药水中含有毒的药水。老鼠2未中毒,说明2、3、6、7无毒。老鼠3中毒,说明1、3、5、7中有一瓶有毒。所以有毒的为5号药水,其实和直接将二进制转化为十进制的结果是一样的。

回到正题,如果有1000瓶药水,则需要10只老鼠,因为10位二进制足以表示0-999。


点击面试手册,获取本站面试手册PDF完整版