问题描述

现在实验室有1000瓶药水，其中999瓶是无毒的，只有1瓶是有毒的，但是从外观上看无法分辨。喝下毒药的小白鼠，在一星期后会突然死亡，但在这之前一点症状都没有。现在需要你能够在一星期之后找出哪一瓶是毒药，请问至少需要多少只小白鼠参与实验？

解题思路

这个问题可以转化为二进制编码问题

• 每一瓶药水用一个唯一的二进制编号，编号范围从1到1000（共1000瓶）
• 每只小白鼠对应二进制中的一位
• 设计实验：每只小白鼠喝那些在其对应位为1的编号的药水

由于药水只喂给了对应二进制位置为1的小白鼠，一周后，哪些位置上的小白鼠死了，那么其对应的十进制编号的药水就是毒药了。比如2、3号小白鼠死亡，其二进制为 0 0 0 0 0 0 0 1 1 0 对应的十进制数字为 6，判定6号药水有毒。

结论

• 最少需要 10 只小白鼠 即可在一周后准确找出毒药
• 10 只小白鼠最多可以区分 =1024 种状态，足以覆盖 1000 瓶药水的所有可能