一道算法题
闲来无聊在网上找题目练练。
碰到一道笔试题：
有16瓶水，其中只有一瓶水有毒，小白鼠喝一滴之后一小时会死。请问最少用__只小白鼠，在1小时内一定可以找到至少14瓶无毒的水？
1.一开始设想任意组合14瓶水，共有120种可能，如果每种可能都尝试了，那么肯定可以找到14瓶无毒的水了，不过明显效率太差，白白浪费了小白鼠。
2.后来发现其实任意组合15瓶水，那么其实只需要16只就可以找到哪瓶有毒了。然而题目只需要找14瓶无毒的水，这样是找出来15瓶，明显浪费了。
3.这会就想到将水两两组合，共有8对，那么8只就可以得到14瓶无毒的水了。这感觉不错诶。
4.从开始一直以来就有一个潜意识感觉就是，小白鼠只死了一只，貌似也没有得到最大使用啊；这会突然觉得或许应该组合小白鼠。
4.然后就想到8对，就是8种可能，只需要3只就可以组合出8种可能，那么怎么组合呢？
设想8对水从0-7标号，编号为000-111，3只小白鼠设为A、B、C。
A喝第一个编号为1的，B喝第二个编号为1的，C喝第三个编号为1的，
那么A喝了100,101,110,111
B喝了010,011,110,111
C喝了001,011,101,111
出现中毒的情况分为8中，也设为000-111，000即为都没有中毒，111即为都中毒。第一个二进制数表示A的中毒情况，第二个表示B的中毒情况，第三个表示C的中毒情况。
如果中毒情况是000，那么毒水就在编号000的那对水里，其它7对共14瓶水都是无毒的。
随便选一个110，即A与B都中毒了，C没有中毒，那么可以排除001,011,101,111，可选的为来自A的判断：100，110。来自B的判断：010,110，那么可以知道毒水在110。
即中毒情况与水的编号对应。
可以对照下图来理解：
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
