有 1000 瓶药物，但是其中有一瓶是有毒的，小白鼠吃了一个星期以后就会死掉！请问，在一个星期内找出有毒的 药物，最少需要多少只小白鼠？

有 1000 瓶药物，但是其中有一瓶是有毒的，小白鼠吃了一个星期以后就会死掉！请问，在一个星期内找出有毒的 药物，最少需要多少只小白鼠？

天堂之鼠

文章目录

• 天堂之鼠
• 原题题目（某个面试题）：
• • 有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
  • 以下给出两种思路：
• 一、二分法（用树遍历）
• 二、二进制
• • 1.药水小鼠分类
  • 2.按照小鼠死亡情况写二进制

原题题目（某个面试题）：

有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？

以下给出两种思路：

一、二分法（用树遍历）

首先我们看到这个题，最基本的想法就是一个小鼠肯定喝多个药水，不然1000个药水999个小鼠意义何在(^_−)☆

其次就是怎么去划分的问题？？？ 那么你可能会想到算法，想到树。

这里我们拿计算机内存来说
一个16位宽度的位址总线可以寻址到2的16次方=65536=64KB的内存位址，而一个32位位址总线寻址到2的32次方4,294,967,296=4GB的位址。

那么现在假设有8瓶药水，很明显你知道至少需要3个小鼠，那么怎么去分配？？？

在这里采用二分法把1-8分成两部分，1-4和5-8，让小鼠1喝1-4 药水如果小鼠1死了就说明毒药在1-4之中
继续二分， 1-4分为1，2和3,4但是要注意让小鼠2喝 1,2，5,6（必选上一分支的一半）之后让小鼠3喝1,3，5,7
如果小鼠1死了说明毒药在1-4中，如果小鼠2死了忽略喝掉无毒的5 ,6， 毒药在1和2中。 如果小鼠3死了说明1是毒药。

那么同理1-1000个药水，依次二分
1-500 501-1000。 1-250 , 251-500，501-750， 751-1000 …
依次二分用树遍历总共10层，也就是2的10次方 = 1024 > 1000.完成遍历同时第一个小鼠喝1-500，第二个小鼠喝1-250和501-750…依次下去

二、二进制

同样这种方法也是应用2的n次方，2的10次方= 1024 >1000.

1.药水小鼠分类

将药水编号按二进制排列，并且一共10位对应10只小鼠，如图：
个位对应小鼠10，依次类推：

小鼠10喝掉所有对应二进制第一位是1的药水即：编号为1 3 5 7 …的
小鼠 9 喝掉所有对应二进制第二位是1的药水即：编号为2 3 6 7 …的
依次类推…

2.按照小鼠死亡情况写二进制

在编号喝药水之后，我们观察老鼠死亡情况一旦有老鼠死亡，就在对应的二进制位数上置1，不死置0，得到的就是毒药水编号对应的二进制。

那么肯定有小伙伴问为什么呢？？？？？？？？？？？？

我们来假设7号是毒药水，其二进制为0000 0111，那么凡是喝过7号的都得上天堂∑(っ°Д°;)っ卧槽，不见了，对应的有1的位数也就是小鼠8，小鼠9，小鼠10都会上天堂。所以对应位数就会置1.