4只老鼠和1瓶毒药---经典面试题详解

2018-07-10 本文已影响121人深渊漫步者亚尔特留斯

有15个瓶子，其中最多有一瓶有毒，现在有四只老鼠，喝了有毒的水之后，第二天就会死。如何在第二天就可以判断出哪个瓶子有毒?

思路

给老鼠喂食后，老鼠有生存和死亡两种状态，即0和1，4只老鼠既有16种组合。只要分配恰当，即可完美解决。

将15个瓶子编号，然后将十进制的编号转为二进制

转换表.jpg

将二进制号码第一位为1的瓶子给1号老鼠，第二位为1的瓶子给2号老鼠，依次下去分配给4只老鼠。

分组.png

即：

1号老鼠喝 1，3，4，7，9，11，13，15
2号老鼠喝 2，3，6，7，10，11，14，15
3号老鼠喝 4，5，6，7，12，13，14，15
4号老鼠喝 8-15

根据4只老鼠的状态得出哪个瓶子有毒。

例如：2号老鼠死了，其他生存，二进制为0010，转十进制即2，结论为2号瓶子有毒。

再例如：3号老鼠生存，其余死亡，二进制为1011，转十进制即11，结论为11号瓶子有毒。

老鼠喝毒药这题目还有一种变种：
有16瓶水，其中只有一瓶水有毒，小白鼠喝一滴之后一小时会死。请问最少用（）只小白鼠，在1小时内一定可以找出至少14瓶无毒的水？
A:1,B:3,C:4,D:16
答案是B。解法有两种。

图解.png

在牛客网看到的。。。
如图所示，将16瓶水分别标号为1~16，2瓶为一组，分为8组,为：A1是第1、2瓶水，以此类推……A8为第15、16瓶水

图中三个圆圈分别为3个小白鼠

小白鼠1喝 A1、A4、A5、A7
小白鼠2喝 A2、A4、A6、A7
小白鼠3喝 A3、A5、A6、A7

若仅小白鼠1死，则有毒水在A1组
若仅小白鼠2死，则有毒水在A2组
若仅小白鼠3死，则有毒水在A3组
若仅小白鼠1、2死，则有毒水在A4组
若仅小白鼠1、3死，则有毒水在A5组
若仅小白鼠2、3死，则有毒水在A6组
若小白鼠都死，则有毒水在A7组
若小白鼠都不死，则有毒水在A8组

综上所述，只需3只小白鼠即可在1小时内一定可以找出至少14瓶无毒的水

在查找资料的时候，看到有网友审题不清，没看清是限时的，写出了以下答案：

我觉得可以这么做呀，让一只小白鼠每隔一分钟喝一瓶水中的一滴，然后看小白鼠是在一个小时后第几分钟死掉的，这样只需要一只不就可以了？

是不是觉得思路惊奇，但又观点很赞呢，哈哈!