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

有目录，不迷路

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

出题

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

言归正传，下面分享一道很有意思的面试题：

从前有个国王要举办一个宴会，准备了1000瓶酒。有个刺客要刺杀国王，在一瓶酒中下了毒，然后就被抓住了，刺客招供有一瓶酒中有毒，但是刺客自己也不知道在哪瓶酒里下了毒。国王不想终止宴会，就想到一个办法找死囚过来试酒从而找出毒酒，但是距离晚宴还有2个小时就要开始，而毒发身亡的时间需要1个半小时（意味着只有一次毒发的机会），国王最后想了一个办法，只用了极少数的死囚数量就试出了毒酒，请问用了多少个死囚？是怎么试的？（假设不管怎么喝每瓶酒都不会喝光）

当然，本题可以说是一个思想实验，因此忽略掉道德评判的因素。

回答

看到这个题目，大家可能就八仙过海 —— 各显神通了。

有些人可能就会说了：这个问题还不简单吗？本国王财大气粗，人力资源丰富，立马召集1000名死囚，一人一瓶喝一口，一个半小时后死的那名死囚喝的那瓶酒就是毒酒。什么？极少数的死囚？都说了本国王财大气粗，1000名死囚对于本国王来说就是极少数的死囚。

当然，也有人会说既然距离晚宴还有两个小时，而毒发时间为一个半小时，也就是说我们还有半个小时也就是30分钟喝酒的时间。那我们来卡时间好了，我们按照保守估计来算：

假设一名死囚需要花30秒喝一瓶酒里面的一口酒，然后再等待1分钟喝下一瓶酒。也就是说一名死囚喝一瓶酒需要一分半的时间，三十分钟能喝20瓶酒。因此1000瓶酒需要 1000/20 约等于 50名死囚。这还只是保守估计，比上个憨憨1000的答案不知道少了多少。然后，我们只需要看是哪个死囚死了，再根据他的死亡时间推算即可。简直完美有木有？

首先，答案是1000的哪怕当了国王也是个憨憨国王，虽然这种方法一定可以试出哪瓶是毒酒。其次，根据死亡时间推断的肯定是侦探悬疑题材类的小说或者影视作品看多了。根据死亡时间推断似乎有一定的道理，但是每个人的体质是不一样的，所以毒发的时间也是不一样的， 一个半小时的时间只是个大概的时间，所以50的答案也不完美，甚至很可能会出错。而一旦出错，就是几百上千条人命。

那么这个题目该如何解呢？

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

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

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

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

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

我们看这两句就好了：

1. 对数是对求幂的逆运算。
2. 如果a的x次方等于N（a>0，且a≠1），那么数x叫做以a为底N的对数（logarithm），记作x=loga N。其中，a叫做对数的底数，N叫做真数。

举个栗子好了：

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

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

那么，log1000(以2为底)到底是多少呢？

答：2的多少次方是1000就是多少！！！

而2的9次方是512，2的10次方是1024（熟悉的1024），所以log1000(以2为底)位于 9 - 10 之间，也就是9点多。

看到这里你可能还是很懵。好吧，log1000(以2为底)这个的值我知道是怎么算出来的了，但是这个log1000(以2为底)是怎么得出来的，而且这个答案为10比起1000或者说是50也太少了吧，简直不科学，不可能呀！

不要急，这个就是正确答案。至于个中缘由，请听我接下来娓娓道来！！！

信息熵

如果用一句话来概括本文中的问题：无非是国王想要弄清楚1000瓶酒中哪一瓶是毒酒，国王不确定1000瓶酒中哪一瓶是毒酒 好像是句废话 。我们往上走一层，也就是说国王想要弄清楚一件非常非常不确定的事情。

如果从信息的角度来理解，一件事情的不确定性就等于它的信息量，而我们通常用信息熵来实现信息的度量（具体可以参照吴军博士《数学之美》的第6章<信息的度量和作用>）

《数学之美》pdf 百度网盘链接分享
链接：https://pan.baidu.com/s/1dQ08nWsSmyuMDhesIYv_Vw
提取码：yxaf

看起来信息熵的概念似乎很玄学。但是没关系，吴军博士在《数学之美》中举了一个很通俗易懂的例子，以下是原文（写不动了，最近缺乏小伙伴们的支持和鼓励，容我偷个小懒）：

来看一个例子。2010 年举行了世界杯足球赛，大家都很关心谁会是冠军。假如我错过了看世界杯，赛后我问一个知道比赛结果的观众“哪支球队是冠军”?他不愿意直接告诉我，而让我猜，并且我每猜一次，他要收一元钱才肯告诉我是否猜对了，那么我需要付给他多少钱才能知道谁是冠军呢?我可以把球队编上号，从1到32，然后提问:“ 冠军的球队在1-16号中吗?”假如他告诉我猜对了，我会接着问:“冠军在 1-8号中吗?”假如他告诉我猜错了，我自然知道冠军队在9-16号中。这样只需要五次，我就能知道哪支球队是冠军。所以，谁是世界杯冠军这条消息的信息量只值5块钱。

是不是跟二分查找的理念是一样的呢？

二分查找的话，可以查看我的这篇博客的第一章就是了：
肝了几万字，送给看了《算法图解》却是主攻Java的你和我（上篇）

而二分查找的时间复杂度为logN(以2为底)。在上文中，假设每支球队夺冠概率相同的话，如果要保证一定能猜出32只球队中的冠军队伍，我只需要5次，也就是log32(以2为底)。那么，国王想要一定能找出1000瓶毒酒中的哪一瓶毒酒，只需要查找log1000(以2为底)次，也就是9点多次。因为一定要找出，9次可能找不完，所以需要10次。

这个时候可能很多小伙伴就开始跃跃欲试了：我知道了，我知道了

我们来把1000瓶酒按照 1 - 1000进行编号，那我们只需要10次就可以试出毒酒了：

1. 第一次，安排1名死囚，分别品尝编号为 1-500 的酒。如果这名死囚毒发身亡，则毒酒在编号为1 - 500酒中；反之，则在另外500瓶酒中。
2. 第二次，再安排1名死囚，分别品尝编号为 1 - 250 的酒。（在这里，我们也假设这名死囚毒发身亡）。
3. 第三次，再次安排1名死囚，分别品尝编号为 1 - 125瓶的酒。（这里，我们还是假设这名死囚毒发身亡）。
4. 第四次，再再次安排1名死囚，分别品尝编号为 1 - 63瓶的酒。（在这里，我们还是假设这名死囚毒发身亡）。
5. 第五次，再再再次安排1名死囚，分别品尝编号为 1 - 32瓶的酒。（在这里，我们还是假设这名死囚毒发身亡。如果没有人毒发身亡毒酒就在另外的31瓶酒里。）。

好了，到了久违的32。根据上文我们可以知道还需要5次就一定可以判断出毒酒是哪瓶！总次数，也就是 5 + 5 = 10次！！！

那么，按照这种方法需要的死囚人数最多为10名（毕竟如果这名死囚没有毒发身亡的话，就可以接着试酒）。

哦，原来这个就是正确答案的由来呀！！！

不过这个时候可能有小伙伴就会发现不对劲了

等等，这个方法我确实是理解了。但是这样的话：

• 耗时：一个半小时 * 10 = 15个小时。

what???需要十五个小时，那我等到能吃酒席的话，黄花菜都凉了。

所以本章节讲的全都是废话吗？

当然不是！

那如果不是废话的话，为什么完全无法达到想要的效果呢？

因为我们现在还停留在十进制的世界。

下面，欢迎来到二进制的世界！！！

二进制

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

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

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

但其实不然！

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

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

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

那么问题来了，什么是比特呢？

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

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

这里我们为了节省空间，就假设只有8只球队好了，32支球队、64支球队都可以以此类推。

经过上述分析，猜出8支队伍中冠军队伍的信息熵为log8(以2为底)，也就是3比特，3个二进制位。而获得冠军队伍可能的结果：总共为8种情况。刚好可以用3个二进制位表示。

如下表，3个二进制位刚好可以表示8种情况：

十进制二进制00 0 010 0 120 1 030 1 141 0 051 0 161 1 071 1 1

或者说，我们刚好可以用3个二进制位给这8支球队编号。（二进制是从0开始计数）

那么，按照二进制的思维该如何解这个“国王试毒酒”问题呢？

破案

大家好，我是狄仁杰，我来破案了。

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

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

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

那么，到底该怎么试呢？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

显然：

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

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

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

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

• 若死囚甲乙丙都死，则他们的二进制位全都表示为1，也就是 111。对应十进制的7，也就是酒7为毒酒。
• 若死囚甲乙丙都不死，则他们的二进制位全都表示为0，也就是 000。对应十进制的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。

怎么样？感受到二进制的神奇和美妙了吗？

回归数学

当然，神奇归神奇，那么到底为啥子可以这样呢？为此，我还特意请教了一位数学专业的小学妹。她从集合的角度分析倒给了我一个全新的思考视角。

一名死囚可以表示的情况为2种：

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

三名死囚可以表示的情况为8种：

以此类推即可。

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

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

最后

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

工作以后，可以用来写博客的时间也变少了。各位小伙伴们，如果觉得这篇博客写的还不错的话，欢迎各位点赞、评论以及加关注哦。这样本博主才更有动力给大家带来更多的优质博客。