信息论之老鼠试毒问题

喜欢ヅ旅行 2023-07-12 08:53 32阅读 0赞

## 前言 ##

最近看到网友讨论一个关于信息论的面试题，原题如下：

> 1000瓶酒其中1瓶有毒,10只老鼠找出毒酒，需要注意每只老鼠只可以试1次？

当然这个题目也有变种：

> 1000瓶酒其中1瓶有毒,使用老鼠来试毒，需要注意每只老鼠只可以试1次，最少需要多少只老鼠？

虽然，题目不同，实际上还是同样的原理。这个题目在网上有很多的解答，可是我觉得讲解的不够通俗易懂，所以准备按照自己的理解来讲解一下原理

## 如何使用老鼠试毒讲解 ##

首先原题目的问题规模实在太大，所以我选择改为8瓶酒其中1瓶有毒，3只老鼠找出毒酒。这里改为8选1使用3只老鼠是因为2^3=8，原理下面会讲。

1.  首先我们给每瓶酒进行编号，从0开始编号，并转化为二进制：

1.  给每只老鼠进行编号，分别为1、2、3，根据编号，喝酒瓶编号二进制值对应位数为1的酒的混合液，如下所示：

1.  上面的内容有点难理解，可以理解为

*  1号鼠喝4,5,6,7号酒的混合物
 *  2号鼠喝2,3,6,7号酒的混合物
 *  3号鼠喝1,3,5,7号酒的混合物
 *  0号酒无老鼠喝

1.  然后进行情况的穷举

*  无老鼠死亡，由于试毒的老鼠已经把1到7号酒都喝过了，所以0号酒有毒
 *  1号鼠死亡，其他老鼠没死，这样根据情况可以推断，只有1号酒其他老鼠没喝过，所以3号酒有毒
 *  2号鼠死亡，其他老鼠没死，同理可得2号酒有毒
 *  3号鼠死亡，其他老鼠没死，同理可得1号酒有毒
 *  1,2号鼠死亡，3号鼠没死，找出1,2号鼠喝过，而3号鼠没喝过的酒，也就是6号酒有毒
 *  1,3号鼠死亡，2号鼠没死，同理可得5号酒有毒
 *  2,3号鼠死亡，1号鼠没死，同理可得3号酒有毒
 *  1,2,3号鼠全灭，由于只有1瓶酒有毒，所以就是它们都喝过的酒，也就是7号酒

1.  分析上面的穷举情况可以看到有一个规律，实际上有毒的酒的编号就是找出死去老鼠喝的相同的酒的编号。我们可以将死去老鼠的编号对应的二进制位取1，没死的老鼠编号对应的二进制位取0。例如1,2号鼠死亡，就是011，转为十进制就是3号酒。

## 最少需要多少老鼠试毒解答 ##

由于酒的数量对应的二进制码的每1位都需要2只老鼠来进行试毒，所以2^n瓶酒最少需要n只老鼠来进行试毒。