有 1000 瓶药物，但是其中有一瓶是有毒的，小白鼠吃了一个星期以后就会死掉！ _二进制

天堂之鼠
文章目录一、二分法（用树遍历）二、二进制
原题题目（某个面试题）：有 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，得到的就是毒药水编号对应的二进制。
那么肯定有小伙伴问为什么呢？？？？？？？？？？？？
【有 1000 瓶药物，但是其中有一瓶是有毒的，小白鼠吃了一个星期以后就会死掉！】我们来假设7号是毒药水，其二进制为0000 0111，那么凡是喝过7号的都得上天堂∑(っ°Д°;)っ卧槽，不见了，对应的有1的位数也就是小鼠8，小鼠9，小鼠10都会上天堂。所以对应位数就会置1.