最近有和同学在讨论用小老鼠来找出有毒的水瓶的问题，稍微总结一下。
经典问题. 16选1
16瓶水其中有一瓶有毒，多少个小老鼠可以确定是哪瓶呢？
1. 二进制编码水瓶
对16瓶水进行4位二进制编码，前15瓶分别用1到15的编码，第16瓶用0000。每只小老鼠对应一个比特位，从低位到高位编号，哪一位是1，就给对应的小老鼠喝这瓶水。比如第五瓶是0101，就给第一只和第三只喝；如果最后只有这两只死亡，拼出的编码也是0101，就能确定第五瓶有毒。如果四只都存活，就是编码0000的第16瓶有毒。
2. 减半查找
如果不考虑时间，我们也可以一轮一轮地测试。每次用一只小鼠喝候选水瓶中的一半，根据死亡与否判断毒水在哪一半，再继续缩小范围。所以最多需要log2(n)向上取整只小鼠。
3. 上面两种方式等价。
每得到一个比特位的结果，就能排除一半候选，4位结果正好可以区分16瓶水。区别在于，二进制编码可以让4只小鼠同时测试，减半查找则需要根据上一轮的结果继续测试。
变体问题
- 如果10-17瓶水只有一瓶水有毒，同样可以按照1的方式进行计算，其中10到16瓶需要4只，17瓶需要5只。
- 如果16瓶水，其中有一瓶是有毒的，要找14瓶没毒的，实际上就可以变相的理解为8瓶水中找7瓶，从而只需要三只小老鼠就可以了。
- 如果允许有两轮，比如有一个小时时间，小鼠喝毒药后恰好半个小时去世，那么每只小鼠有第一轮死亡、第二轮死亡、两轮都存活三种结果。这样可以改用三进制编码：每一位分别决定第一轮喝、第二轮喝或者不喝。3只小鼠有3^3=27种结果，所以16瓶水可以用3只小鼠在两轮内确定。
如果以后还有再继续补充吧～