扫码关注微信公众号
回复“面试手册”,获取本站PDF版
回复“简历”,获取高质量简历模板
回复“加群”,加入程序员交流群
回复“电子书”,获取程序员类电子书
这个问题不太容易想到可以先记住答案,需要老鼠的数量为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。
本站链接:https://www.mianshi.online,如需勘误或投稿,请联系微信:lurenzhang888
点击面试手册,获取本站面试手册PDF完整版