小学妹听了都说棒的：国王试毒酒问题

数学是上帝描述自然的语言

有目录，不迷路

• 出题
• 回答
• 信息熵
• 二进制
• • 破案
• 回归数学
• 最后

出题

好吧，我承认我有些标题党了。醒醒吧，你哪来的小学妹，作为程序猿的你身边明明都是大老爷们！！！

那么这个题目该如何解呢/p>

我们都知道一般的解题教程都是先给出思路以及解题过程，再得出答案。这里我们反其道而行之，先给出答案：

试出1000瓶葡萄酒中的一瓶毒酒所需要的死囚数为：log1000(以2为底)，答案应该为9点多，但是人不能论半个，所以向上取整也就是10名。

这个时候可能大家就会有一个疑问了：log1000(以2为底)是9点多是怎么算出来的/p>

懂对数运算的小伙伴们下面就可以忽略了

这里先给大家简单介绍一下对数运算，以下是百度百科的官方解释：

log1(以2为底)的值是多少这个栗子中2为底数，1为真数，答案为x，也就是2的多少次方是1，答案就是多少。而我们都知道除0以外的任何数的0次方都为1，所以log1(以2为底)的值是0。

以下是logx(以2为底)的函数图(右半部分)：

如果你看到上图中的话，不禁心中生出一个疑问：那另外八种人呢么不好意思，你属于不懂二进制的人，因为二进制中的2表示为 10。

曾几何时，我以为这句话只是单纯用来装（A和C之间）来用的。

曾几何时，我也天真的认为十进制天然要比二进制要高级得多 。

但其实不然！

当然，在我的这篇博客 实现两个数互换的八种方法 的章节中曾经提到过：

计算机中没有我们所谓的2、3、4、5 … 100 … 1000 … ，计算机中有的只是0和1，逢二便进一。

那么，二进制和信息熵有啥子关联吗们试着追根溯源：原来，信息熵的概念是1948年香农在他那非常著名的论文《通信的数学原理》中提出来的。而香农并不是用次数(比如猜出32球队中的冠军队伍为5次、1000瓶毒酒需要10次)来度量信息量的，而是用比特(Bit)这个概念！

那么问题来了，什么是比特呢/p>

其实，一个比特就是一个二进制位！

就拿吴军博士举的这个球队的栗子好了。

为了方便大家思考，我们从头开始分析

1. 假设是1瓶酒，因为这瓶酒肯定是毒酒，所以需要0名死囚品尝这一瓶酒。
2. 假设是2瓶酒，我们不确定哪瓶酒有毒。只需要一名死囚品尝其中一瓶酒：若死囚身亡，则品尝的酒有毒；反之，则另一瓶酒有毒。
3. 假设是3瓶酒，我们不确定哪瓶酒有毒。这个时候一名死囚明显就不够用了撒，就需要再加一名死囚。

所以，我们通过以上分析可以得出：一名死囚所能试出毒酒的最多瓶数为2瓶，也就是2的1次方。换言之，2瓶酒的信息熵为log2(以2为底)，也就是1比特，为一个二进制位。

那么，到底该怎么试呢/p>

这里，我们将一名死囚对应一个二进制位，将酒分别用二进制进行编号。如下表：

十进制	二进制位1
酒的编号	死囚甲
0	0
1	1

通过上述分析，我们已经知道了：在两瓶酒的情况下，只要死囚甲随便选择一瓶喝就可以试出哪一瓶是毒酒。

因为二进制只有0和1两种情况，而死囚对于一瓶酒也只有两种情况：喝，或者不喝。

而作为创造万物的程序员，这里我们可以很容易的设定一个规则：当死囚对应的二进制位为1时喝，为0时不喝（当然，你也可以反过来）。也就是说，在上表中，编号为0的酒，我们简称酒0，不让死囚甲喝；而酒1则死囚甲喝。

若是，死囚甲毒发身亡，则酒1有毒；反之，则酒0有毒。

同样的，2名死囚可以表示2的2次方，也就是试出4瓶酒；或者说，4瓶酒的信息熵为log4(以2为底数)也就是2Bit，2个二进制位。

我们也可以用表格表示出来：

十进制	二进制位2	二进制位1
酒的编号	死囚乙	死囚甲
0	0	0
1	0	1
2	1	0
3	1	1

同样的，死囚对应的二进制位为1时喝，为0时不喝。也就是说，死囚甲需要喝酒1和酒3，死囚乙需要喝酒2和酒3。

那么，如果这样的话，我们该如何根据身亡情况来判定毒酒呢/p>

其实，很简单：如果某名死囚身亡，那么毒酒一定在他喝的那些酒中；反之，如果某名死囚没身亡，那么毒酒一定不在他喝的那些酒中。

而根据我们的规则：某名死囚对应的二进制位为1，则表示喝；为0，则表示不喝。所以，每瓶酒是毒酒所对应的情况分别为：

十进制	二进制位2	二进制位1
酒的编号	死囚乙(状态)	死囚甲(状态)
0	0 (生)	0 (生)
1	0 (生)	1 (死)
2	1 (死)	0 (生)
3	1 (死)	1 (死)

显然：

1. 若是甲乙双生，则对应的二进制位为，也就是酒0为毒酒。
2. 若是乙生甲死，则对应的二进制位为，也就是酒1为毒酒。
3. 若是乙死甲生，则对应的二进制位为，也就是酒2为毒酒。
4. 若是甲乙双死，则对应的二进制位为，也就是酒3为毒酒。

同样的，三名死囚可以表示出2的3次方也就是8瓶酒。

十进制	二进制位3	二进制位2	二进制位1
酒的编号	死囚丙	死囚乙	死囚甲
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

同样的，死囚所对应的二进制位为1，表示喝；为0，则表示不喝。

• 若死囚甲乙丙都死，则他们的二进制位全都表示为1，也就是 。对应十进制的7，也就是酒7为毒酒。
• 若死囚甲乙丙都不死，则他们的二进制位全都表示为0，也就是 。对应十进制的0，也就是酒0为毒酒。

那么通过以上种种，我们来类推一下

1. 试出1瓶酒中的一瓶毒酒，需要0名死囚，也就是log1(以2为底)。
2. 试出2瓶酒中的一瓶毒酒，需要1名死囚，也就是log2(以2为底)。
3. 试出3瓶酒中的一瓶毒酒，需要2名死囚，也就是log3(以2为底)，向上取整为2。
4. 试出4瓶酒中的一瓶毒酒，需要2名死囚，也就是log4(以2为底)。
5. 试出5瓶酒中的一瓶毒酒，需要3名死囚，也就是log5(以2为底),向上取整为3。
   …
6. 试出8瓶酒中的一瓶毒酒，需要3名死囚，也就是log8(以2为底)。
   …

所以，试出1000瓶酒中的一瓶毒酒，需要10名死囚，也就是log1000(以2为底)，,向上取整为10。

两名死囚可以表示的情况为4种：

以此类推即可。

其实这个数学问题，被称为 幂集，也就是求集合中所有的子集（包括全集和空集）构成的集族。因为每个子集都有两种情况：选，或者不选。所以，n个子集所对应的情况为： 2的n次方，而一种情况恰好对应着唯一的一瓶酒。是不是和之前的分析有着异曲同工之妙呢/p>

关于图片：没办法，画图软件处理不好图层之间的关系，我就只好手画了，哈哈。

最后

不知不觉，一篇博客就肝到了凌晨一点半左右：

来源：古阙月