今天要和大家讨论的是“小白鼠试毒问题”，据说是腾讯公司面试题，听上去挺吓人，其实大可不必担心，只要你顺着讲解的思路稍微开动一下脑筋，你就会发现：原来如此简单，你也会做这道“小白鼠试毒问题”的腾讯面试题！
原问题是这样的：现有1000瓶药水，其中一瓶是毒药，只要一小滴，就可让小白兔24小时内死亡；如果用小白兔来试毒，怎样在最短时间内用最少的小白兔，找出这瓶毒药？
原题目中的药水1000瓶，难度太大，我把它改成了100瓶；而且，用小白兔来试毒也与现实中用小白鼠试毒相距甚远，我把小白兔改成了小白鼠；更重要的是：原来的解法不尽完善，不但有疏误之处，而且过于简略，不容易理解。所以，我用我的方式重新解答一番，希望大家喜欢、能够有所收获。
现在的问题是：
有100瓶药水，其中一瓶是毒药，只要一小滴，就足以让小白鼠24小时内死亡，而无毒的药水，小白鼠可承受的剂量为100滴；如果用小白鼠来试毒，怎样在最短时间内用最少的小白鼠，找出这瓶毒药？
这个问题有两个要求，一是时间要最短、二是试毒小白鼠的数量要最少，如果两个要求同时考虑，不容易找到突破口。如果只考虑时间最短，最简单的办法就是“一一对应编号”：把100瓶药水从1到100依次编号，小白鼠也从1到100依次编号，然后，1号小白鼠喂一滴1号药水、2号小白鼠喂一滴2号药水、……、100号小白鼠喂一滴100号药水，24小时之后，几号小白鼠中毒身亡，几号药水就是毒药。这个办法叫做“一一对应法”，非常容易操作，而且时间最短（不可能比耗时一天再短了）；缺点是小白鼠用得太多、需要100只小白鼠参与试毒，如果没有那么多小白鼠怎么办？
再认真考虑一下，你会发现其实用不了100只小白鼠，99只就够了：我们可以先把第100号药水暂时撇开不管，而从1到99号药水，按照它们的编号分别给小白鼠喂药，几号药水就给几号小白鼠就喂它一滴，24小时之后，几号小白鼠中毒身亡，几号药水就是毒药；如果99只小白鼠没有一只中毒身亡，那毫无疑问，肯定就是100号药水是毒药！不过，99只小白鼠还是太多了。
如果不考虑时间，只考虑小白鼠数量最少，我们也可以只用一只小白鼠完成试毒工作：第1天喂一滴1号药水，24小时后如果没被毒死，第2天再喂一滴2号药水，……；哪天它被毒死了，头天喂的那瓶药水就是毒药；最多花99天，就知道哪瓶药水是毒药了。这个办法叫“逐一排除法”，好处很明显，缺点是时间拖得太长，最坏的情况需要花99天，有时候还真等不起。
能不能折中一下，兼顾时间与小白鼠数量两个方面呢？像这种涉及到最大最小或者最多最少的“极值问题”或“最优化问题”，有一种“二分法”又称“对半法”，可以试试：把100瓶药水一分为二，均分成两组，1号至50号为A1组，51号至100号为A2组，……
然后随便挑选一只小白鼠对A1组进行试毒，A2组暂时撇开不管；把A1组中的每瓶药水都喂这只小白鼠一滴，24小时过后，如果小白鼠不幸中毒身亡，那就说明有毒的药水在A1组；如果小白鼠侥幸逃脱，那就说明有毒的药水在A2组，接着下一步，就要再用这只活着的小白鼠对有毒的A2组继续试毒。但最坏的情况是：在这第一步，第一只小白鼠就已经不幸中毒身亡，A1组是有毒组，需要另选第二只小白鼠对A1组继续用“二分法”试毒。
把A1组中50瓶药水一分为二，均分成两组，1至25号为B1组，26至50号为B2组，由于第一只小白鼠已经“牺牲”，需要另选第二只小白鼠对B1组进行试毒，B2组暂时撇开不管；把B1组中每瓶药水都喂一滴给第二只小白鼠，24小时过后，如果小白鼠不幸中毒身亡，那就说明有毒的药水在B1组；如果小白鼠侥幸逃脱，那就说明有毒的药水在B2组，紧接着的下一步就要再用活着的第二只小白鼠对有毒的B2组继续试毒。但最坏的情况是：第二只小白鼠在这一步就不幸中毒身亡了，B1组是有毒组，还要另选第三只小白鼠对B1组继续用“二分法”试毒。
把B1组中25瓶药水一分为二，不可能均分就尽可能接近，1至13号为C1组，14至25号为C2组，由于第二只小白鼠也“牺牲”了，需要再挑选第三只小白鼠对C1组进行试毒，C2组暂时撇开不管；把C1组中每瓶药水都喂一滴给第三只小白鼠，24小时过后，如果小白鼠不幸中毒身亡，那就说明有毒的药水在C1组；如果小白鼠侥幸逃脱，那就说明有毒的药水在C2组，下一步还要第三只小白鼠再对有毒的C2组继续试毒。最坏的情况是：在这一步，第三只小白鼠又不幸中毒身亡，C1组是有毒组，还要另选第四只小白鼠对C1组继续用“二分法”试毒。
如此用“二分法”一步步继续分下去、试下去，第四步分组情况是这样的（如图所示）；最坏的情况是：第四只小白鼠又“牺牲”了，D1组是有毒组。
第五步分组情况是这样的（如图所示）；最坏的情况是：第五只小白鼠又“牺牲”了，E1组是有毒组。
第六步分组情况是这样的（如图所示）；最坏的情况是：第六只小白鼠又“牺牲”了，F1组是有毒组。
第七步（也就是最后一步）只剩两瓶，随便拿出来一瓶（假设就是1号瓶吧）让第七只小白鼠试毒，另一瓶（也就是2号瓶）暂时撇开不管；最坏的情况是：第七只小白鼠又“牺牲”了，1号瓶就是毒药水。
换句话说：经过七步，用了7天、牺牲了7只小白鼠，我们终于找出了毒药水；当然，也有可能第七只小白鼠侥幸逃过一劫，那2号瓶肯定就是毒药水。
回过头来比较一下这三种方法：第一种“一一对应法”，需要99只小白鼠同时试毒，只用一天时间，99只小白鼠最后有可能都活着，最多只牺牲1只。
第二种“逐步排除法”：只需要1只小白鼠试毒，时间却可能长达99天，如果时间达到了99天，那么，那只小白鼠最后就活着，如果时间不到99天，那只小白鼠肯定就牺牲了。
第三种“二分法”：需要用7天、预备7只小白鼠，最坏的情况是7只小白鼠全牺牲了（最好的情况是从头到尾只用了一只小白鼠，而且最后还活着）。
如果你对“二分法”感兴趣，不妨考虑一下：假如“二分法”的每一步都同时用两只小白鼠试毒，应该怎样操作？结果又会如何呢？
以上三种方法各有优劣，还有什么更好的办法吗？
办法还是有的，不过，如果你没有学过“二进制数”，可能还真想不到：用二进制编码，只需要用7只小白鼠，最多牺牲其中的6只，而且只用一天，就把毒药水找出来。
什么是“二进制数”呢？我们知道，通常我们使用的都是“十进制数”，有0、1、2、3、4、5、6、7、8、9十个数码，并且“满十进一”；而计算机使用的却是“二进制数”，只有0与1两个数码，并且“满二进一”。
这里有张表，列出了100以内的十进制数与（七位的）二进制数之间的关系。如果你一时看不懂，也不要紧，你只需要记住：每个十进制数都可以化为唯一一个二进制数，每个二进制数也都可以化为唯一一个十进制数。
现在让我们回到原问题：100瓶药水，其中一瓶是毒药；用7只小白鼠试毒，怎样只用一天时间，就找出这瓶毒药？
解答的关键就是“二进制编码”：首先，让我们把100瓶药水从1到100依次编号，7只小白鼠也从1到7依次编号。
然后，暂时撇开第100号药水不管，其余99瓶按如下方式分别给小白鼠喂药：看它的二进制编码第几位上有数字1，第几位上有数字1，就给第几号小白鼠喂一滴药水。比如：第53瓶药水，53的二进制编码为0110101，其第二位上有数字1，就给第2号小白鼠喂一滴药水；第三位上也有数字1，又给第3号小白鼠喂一滴药水；第五位上也有数字1，又给第5号小白鼠喂一滴药水；第七位上还有数字1，再给第7号小白鼠喂一滴药水（想一想：如果53号瓶就是毒药水，那第2号、第3号、第5号与第7号小白鼠必死无疑；反过来，如果最终第2号、第3号、第5号与第7号小白鼠都牺牲了，而且只有这四只小白鼠牺牲，那也就意味着第53号瓶就是毒药！是不是？）。
从1号瓶开始，每瓶药水都依次按它的二进制编码分别给相应的小白鼠喂药，一直到99号瓶喂完为止；24小时过后，如果所有7只小白鼠都侥幸活着，那么第100号药水就是毒药；如果有若干小白鼠不幸中毒身亡，那么，只要根据身亡的小白鼠的编号反过来推算，就可以知道哪瓶药水是毒药。
比如：中毒身亡的小白鼠有三只，编号分别为1号、3号与7号：1号小白鼠对应着二进制编码第一位数字是1，3号小白鼠对应着二进制编码第三位数字是1，7号小白鼠对应着二进制编码第七位数字是1，其余各位上的数字都是0，于是得到一个二进制数1010001，把1010001化成十进制数就是81，即知第81号瓶是毒药。
于是，通过这样的二进制编码，我们只用7只小白鼠、最多牺牲其中6只，只花1天时间就找到了有毒药水。
“二进制编码”的解答过程告诉我们：数学的编码方式非常重要，有时候只要适当改变编码方式，就可以化难为易；当然也可以反过来“化易为难”（比如我们设置某种密码时就需要“化易为难”）
顺便问大家一个问题：，我们用7只小白鼠通过“二进制编码”试毒，花了一天时间在100瓶药水中找出了有毒那一瓶；如果仍然用7只小白鼠，也是只花一天时间，最多可以在多少瓶药水中找出有毒那一瓶？答案是255瓶，不，应该是256瓶！为什么？请大家想想。
最后，留个问题给大家思考，别担心，这个问题不需要用二进制编码：依然是100瓶药水中有一瓶毒药，毒药只要一小滴，就足以让小白鼠24小时内死亡，而无毒的药水，小白鼠可承受的剂量仅为10滴；如果用20只小白鼠来试毒，怎样只花一天时间、只牺牲一只小白鼠，就找出毒药？
今天我们讨论的这个“小白鼠试毒问题”，属于数学中的“极值问题”或“最优化问题”，也属于数学中的“实验设计”问题；我们介绍了四种方法，一一对应法、逐一排除法、二分法（对半法）与二进制编码法，除了二进制编码法稍微困难一点以外，其它方法都还比较容易理解和掌握。
你懂了吗？欢迎你的意见与建议。谢谢大家！
