數(shù)學(xué)是上帝描述自然的語言

有目錄，不迷路

• 出題
• 回答
• 信息熵
• 二進(jìn)制
• • 破案
• 回歸數(shù)學(xué)
• 最后

出題

好吧，我承認(rèn)我有些標(biāo)題黨了。醒醒吧，你哪來的小學(xué)妹，作為程序猿的你身邊明明都是大老爺們！！！

言歸正傳，下面分享一道很有意思的面試題：

從前有個(gè)國(guó)王要舉辦一個(gè)宴會(huì)，準(zhǔn)備了1000瓶酒。有個(gè)刺客要刺殺國(guó)王，在一瓶酒中下了毒，然后就被抓住了，刺客招供有一瓶酒中有毒，但是刺客自己也不知道在哪瓶酒里下了毒。國(guó)王不想終止宴會(huì)，就想到一個(gè)辦法找死囚過來試酒從而找出毒酒，但是距離晚宴還有2個(gè)小時(shí)就要開始，而毒發(fā)身亡的時(shí)間需要1個(gè)半小時(shí)（意味著只有一次毒發(fā)的機(jī)會(huì)），國(guó)王最后想了一個(gè)辦法，只用了極少數(shù)的死囚數(shù)量就試出了毒酒，請(qǐng)問用了多少個(gè)死囚？是怎么試的？（假設(shè)不管怎么喝每瓶酒都不會(huì)喝光）

當(dāng)然，本題可以說是一個(gè)思想實(shí)驗(yàn)，因此忽略掉道德評(píng)判的因素。

回答

看到這個(gè)題目，大家可能就八仙過海 —— 各顯神通了。

有些人可能就會(huì)說了：這個(gè)問題還不簡(jiǎn)單嗎？本國(guó)王財(cái)大氣粗，人力資源豐富，立馬召集1000名死囚，一人一瓶喝一口，一個(gè)半小時(shí)后死的那名死囚喝的那瓶酒就是毒酒。什么？極少數(shù)的死囚？都說了本國(guó)王財(cái)大氣粗，1000名死囚對(duì)于本國(guó)王來說就是極少數(shù)的死囚。

當(dāng)然，也有人會(huì)說既然距離晚宴還有兩個(gè)小時(shí)，而毒發(fā)時(shí)間為一個(gè)半小時(shí)，也就是說我們還有半個(gè)小時(shí)也就是30分鐘喝酒的時(shí)間。那我們來卡時(shí)間好了，我們按照保守估計(jì)來算：

假設(shè)一名死囚需要花30秒喝一瓶酒里面的一口酒，然后再等待1分鐘喝下一瓶酒。也就是說一名死囚喝一瓶酒需要一分半的時(shí)間，三十分鐘能喝20瓶酒。因此1000瓶酒需要 1000/20 約等于 50名死囚。這還只是保守估計(jì)，比上個(gè)憨憨1000的答案不知道少了多少。然后，我們只需要看是哪個(gè)死囚死了，再根據(jù)他的死亡時(shí)間推算即可。簡(jiǎn)直完美有木有？

首先，答案是1000的哪怕當(dāng)了國(guó)王也是個(gè)憨憨國(guó)王，雖然這種方法一定可以試出哪瓶是毒酒。其次，根據(jù)死亡時(shí)間推斷的肯定是偵探懸疑題材類的小說或者影視作品看多了。根據(jù)死亡時(shí)間推斷似乎有一定的道理，但是每個(gè)人的體質(zhì)是不一樣的，所以毒發(fā)的時(shí)間也是不一樣的， 一個(gè)半小時(shí)的時(shí)間只是個(gè)大概的時(shí)間，所以50的答案也不完美，甚至很可能會(huì)出錯(cuò)。而一旦出錯(cuò)，就是幾百上千條人命。

那么這個(gè)題目該如何解呢？

我們都知道一般的解題教程都是先給出思路以及解題過程，再得出答案。這里我們反其道而行之，先給出答案：

試出1000瓶葡萄酒中的一瓶毒酒所需要的死囚數(shù)為：log1000(以2為底)，答案應(yīng)該為9點(diǎn)多，但是人不能論半個(gè)，所以向上取整也就是10名。

這個(gè)時(shí)候可能大家就會(huì)有一個(gè)疑問了：log1000(以2為底)是9點(diǎn)多是怎么算出來的？？？

懂對(duì)數(shù)運(yùn)算的小伙伴們下面就可以忽略了

這里先給大家簡(jiǎn)單介紹一下對(duì)數(shù)運(yùn)算，以下是百度百科的官方解釋：

我們看這兩句就好了：

1. 對(duì)數(shù)是對(duì)求冪的逆運(yùn)算。
2. 如果a的x次方等于N（a>0，且a≠1），那么數(shù)x叫做以a為底N的對(duì)數(shù)（logarithm），記作x=loga N。其中，a叫做對(duì)數(shù)的底數(shù)，N叫做真數(shù)。

舉個(gè)栗子好了：

log1(以2為底)的值是多少？在這個(gè)栗子中2為底數(shù)，1為真數(shù)，答案為x，也就是2的多少次方是1，答案就是多少。而我們都知道除0以外的任何數(shù)的0次方都為1，所以log1(以2為底)的值是0。

以下是logx(以2為底)的函數(shù)圖(右半部分)：

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

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

而2的9次方是512，2的10次方是1024（熟悉的1024），所以log1000(以2為底)位于 9 - 10 之間，也就是9點(diǎn)多。

看到這里你可能還是很懵。好吧，log1000(以2為底)這個(gè)的值我知道是怎么算出來的了，但是這個(gè)log1000(以2為底)是怎么得出來的，而且這個(gè)答案為10比起1000或者說是50也太少了吧，簡(jiǎn)直不科學(xué)，不可能呀！

不要急，這個(gè)就是正確答案。至于個(gè)中緣由，請(qǐng)聽我接下來娓娓道來！！！

信息熵

如果用一句話來概括本文中的問題：無非是國(guó)王想要弄清楚1000瓶酒中哪一瓶是毒酒，國(guó)王不確定1000瓶酒中哪一瓶是毒酒 好像是句廢話 。我們往上走一層，也就是說國(guó)王想要弄清楚一件非常非常不確定的事情。

如果從信息的角度來理解，一件事情的不確定性就等于它的信息量，而我們通常用信息熵來實(shí)現(xiàn)信息的度量（具體可以參照吳軍博士《數(shù)學(xué)之美》的第6章<信息的度量和作用>）

《數(shù)學(xué)之美》pdf 百度網(wǎng)盤鏈接分享
鏈接：https://pan.baidu.com/s/1dQ08nWsSmyuMDhesIYv_Vw
提取碼：yxaf

看起來信息熵的概念似乎很玄學(xué)。但是沒關(guān)系，吳軍博士在《數(shù)學(xué)之美》中舉了一個(gè)很通俗易懂的例子，以下是原文（寫不動(dòng)了，最近缺乏小伙伴們的支持和鼓勵(lì)，容我偷個(gè)小懶）：

來看一個(gè)例子。2010 年舉行了世界杯足球賽，大家都很關(guān)心誰會(huì)是冠軍。假如我錯(cuò)過了看世界杯，賽后我問一個(gè)知道比賽結(jié)果的觀眾“哪支球隊(duì)是冠軍”?他不愿意直接告訴我，而讓我猜，并且我每猜一次，他要收一元錢才肯告訴我是否猜對(duì)了，那么我需要付給他多少錢才能知道誰是冠軍呢?我可以把球隊(duì)編上號(hào)，從1到32，然后提問:“ 冠軍的球隊(duì)在1-16號(hào)中嗎?”假如他告訴我猜對(duì)了，我會(huì)接著問:“冠軍在 1-8號(hào)中嗎?”假如他告訴我猜錯(cuò)了，我自然知道冠軍隊(duì)在9-16號(hào)中。這樣只需要五次，我就能知道哪支球隊(duì)是冠軍。所以，誰是世界杯冠軍這條消息的信息量只值5塊錢。

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

二分查找的話，可以查看我的這篇博客的第一章就是了：
肝了幾萬字，送給看了《算法圖解》卻是主攻Java的你和我（上篇）

而二分查找的時(shí)間復(fù)雜度為logN(以2為底)。在上文中，假設(shè)每支球隊(duì)奪冠概率相同的話，如果要保證一定能猜出32只球隊(duì)中的冠軍隊(duì)伍，我只需要5次，也就是log32(以2為底)。那么，國(guó)王想要一定能找出1000瓶毒酒中的哪一瓶毒酒，只需要查找log1000(以2為底)次，也就是9點(diǎn)多次。因?yàn)橐欢ㄒ页?#xff0c;9次可能找不完，所以需要10次。

這個(gè)時(shí)候可能很多小伙伴就開始躍躍欲試了：我知道了，我知道了

我們來把1000瓶酒按照 1 - 1000進(jìn)行編號(hào)，那我們只需要10次就可以試出毒酒了：

1. 第一次，安排1名死囚，分別品嘗編號(hào)為 1-500 的酒。如果這名死囚毒發(fā)身亡，則毒酒在編號(hào)為1 - 500酒中；反之，則在另外500瓶酒中。
2. 第二次，再安排1名死囚，分別品嘗編號(hào)為 1 - 250 的酒。（在這里，我們也假設(shè)這名死囚毒發(fā)身亡）。
3. 第三次，再次安排1名死囚，分別品嘗編號(hào)為 1 - 125瓶的酒。（這里，我們還是假設(shè)這名死囚毒發(fā)身亡）。
4. 第四次，再再次安排1名死囚，分別品嘗編號(hào)為 1 - 63瓶的酒。（在這里，我們還是假設(shè)這名死囚毒發(fā)身亡）。
5. 第五次，再再再次安排1名死囚，分別品嘗編號(hào)為 1 - 32瓶的酒。（在這里，我們還是假設(shè)這名死囚毒發(fā)身亡。如果沒有人毒發(fā)身亡毒酒就在另外的31瓶酒里。）。

好了，到了久違的32。根據(jù)上文我們可以知道還需要5次就一定可以判斷出毒酒是哪瓶！總次數(shù)，也就是 5 + 5 = 10次！！！

那么，按照這種方法需要的死囚人數(shù)最多為10名（畢竟如果這名死囚沒有毒發(fā)身亡的話，就可以接著試酒）。

哦，原來這個(gè)就是正確答案的由來呀！！！

不過這個(gè)時(shí)候可能有小伙伴就會(huì)發(fā)現(xiàn)不對(duì)勁了

等等，這個(gè)方法我確實(shí)是理解了。但是這樣的話：

• 耗時(shí)：一個(gè)半小時(shí) * 10 = 15個(gè)小時(shí)。

what???需要十五個(gè)小時(shí)，那我等到能吃酒席的話，黃花菜都涼了。

所以本章節(jié)講的全都是廢話嗎？

當(dāng)然不是！

那如果不是廢話的話，為什么完全無法達(dá)到想要的效果呢？

因?yàn)槲覀儸F(xiàn)在還停留在十進(jìn)制的世界。

下面，歡迎來到二進(jìn)制的世界！！！

二進(jìn)制

如果你看到上圖中的話，不禁心中生出一個(gè)疑問：那另外八種人呢？那么不好意思，你屬于不懂二進(jìn)制的人，因?yàn)槎M(jìn)制中的2表示為 10。

曾幾何時(shí)，我以為這句話只是單純用來裝（A和C之間）來用的。

曾幾何時(shí)，我也天真的認(rèn)為十進(jìn)制天然要比二進(jìn)制要高級(jí)得多 。

但其實(shí)不然！

當(dāng)然，在我的這篇博客 實(shí)現(xiàn)兩個(gè)數(shù)互換的八種方法 的<異或>章節(jié)中曾經(jīng)提到過：

計(jì)算機(jī)中沒有我們所謂的2、3、4、5 … 100 … 1000 … ，計(jì)算機(jī)中有的只是0和1，逢二便進(jìn)一。

那么，二進(jìn)制和信息熵有啥子關(guān)聯(lián)嗎？我們?cè)囍犯菰?#xff1a;原來，信息熵的概念是1948年香農(nóng)在他那非常著名的論文《通信的數(shù)學(xué)原理》中提出來的。而香農(nóng)并不是用次數(shù)(比如猜出32球隊(duì)中的冠軍隊(duì)伍為5次、1000瓶毒酒需要10次)來度量信息量的，而是用比特(Bit)這個(gè)概念！

那么問題來了，什么是比特呢？

其實(shí)，一個(gè)比特就是一個(gè)二進(jìn)制位！

就拿吳軍博士舉的這個(gè)球隊(duì)的栗子好了。

這里我們?yōu)榱斯?jié)省空間，就假設(shè)只有8只球隊(duì)好了，32支球隊(duì)、64支球隊(duì)都可以以此類推。

經(jīng)過上述分析，猜出8支隊(duì)伍中冠軍隊(duì)伍的信息熵為log8(以2為底)，也就是3比特，3個(gè)二進(jìn)制位。而獲得冠軍隊(duì)伍可能的結(jié)果：總共為8種情況。剛好可以用3個(gè)二進(jìn)制位表示。

如下表，3個(gè)二進(jìn)制位剛好可以表示8種情況：

十進(jìn)制二進(jìn)制00 0 010 0 120 1 030 1 141 0 051 0 161 1 071 1 1

或者說，我們剛好可以用3個(gè)二進(jìn)制位給這8支球隊(duì)編號(hào)。（二進(jìn)制是從0開始計(jì)數(shù)）

那么，按照二進(jìn)制的思維該如何解這個(gè)“國(guó)王試毒酒”問題呢？

破案

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

為了方便大家思考，我們從頭開始分析

1. 假設(shè)是1瓶酒，因?yàn)檫@瓶酒肯定是毒酒，所以需要0名死囚品嘗這一瓶酒。
2. 假設(shè)是2瓶酒，我們不確定哪瓶酒有毒。只需要一名死囚品嘗其中一瓶酒：若死囚身亡，則品嘗的酒有毒；反之，則另一瓶酒有毒。
3. 假設(shè)是3瓶酒，我們不確定哪瓶酒有毒。這個(gè)時(shí)候一名死囚明顯就不夠用了撒，就需要再加一名死囚。

所以，我們通過以上分析可以得出：一名死囚所能試出毒酒的最多瓶數(shù)為2瓶，也就是2的1次方。換言之，2瓶酒的信息熵為log2(以2為底)，也就是1比特，為一個(gè)二進(jìn)制位。

那么，到底該怎么試呢？

這里，我們將一名死囚對(duì)應(yīng)一個(gè)二進(jìn)制位，將酒分別用二進(jìn)制進(jìn)行編號(hào)。如下表：

十進(jìn)制二進(jìn)制位1酒的編號(hào)死囚甲0011

通過上述分析，我們已經(jīng)知道了：在兩瓶酒的情況下，只要死囚甲隨便選擇一瓶喝就可以試出哪一瓶是毒酒。

因?yàn)槎M(jìn)制只有0和1兩種情況，而死囚對(duì)于一瓶酒也只有兩種情況：喝，或者不喝。

而作為創(chuàng)造萬物的程序員，這里我們可以很容易的設(shè)定一個(gè)規(guī)則：當(dāng)死囚對(duì)應(yīng)的二進(jìn)制位為1時(shí)喝，為0時(shí)不喝（當(dāng)然，你也可以反過來）。也就是說，在上表中，編號(hào)為0的酒，我們簡(jiǎn)稱酒0，不讓死囚甲喝；而酒1則死囚甲喝。

若是，死囚甲毒發(fā)身亡，則酒1有毒；反之，則酒0有毒。

同樣的，2名死囚可以表示2的2次方，也就是試出4瓶酒；或者說，4瓶酒的信息熵為log4(以2為底數(shù))也就是2Bit，2個(gè)二進(jìn)制位。

我們也可以用表格表示出來：

十進(jìn)制二進(jìn)制位2二進(jìn)制位1酒的編號(hào)死囚乙死囚甲000101210311

同樣的，死囚對(duì)應(yīng)的二進(jìn)制位為1時(shí)喝，為0時(shí)不喝。也就是說，死囚甲需要喝酒1和酒3，死囚乙需要喝酒2和酒3。

那么，如果這樣的話，我們?cè)撊绾胃鶕?jù)身亡情況來判定毒酒呢？

其實(shí)，很簡(jiǎn)單：如果某名死囚身亡，那么毒酒一定在他喝的那些酒中；反之，如果某名死囚沒身亡，那么毒酒一定不在他喝的那些酒中。

而根據(jù)我們的規(guī)則：某名死囚對(duì)應(yīng)的二進(jìn)制位為1，則表示喝；為0，則表示不喝。所以，每瓶酒是毒酒所對(duì)應(yīng)的情況分別為：

十進(jìn)制二進(jìn)制位2二進(jìn)制位1酒的編號(hào)死囚乙(狀態(tài))死囚甲(狀態(tài))00 (生)0 (生)10 (生)1 (死)21 (死)0 (生)31 (死)1 (死)

顯然：

1. 若是甲乙雙生，則對(duì)應(yīng)的二進(jìn)制位為00，也就是酒0為毒酒。
2. 若是乙生甲死，則對(duì)應(yīng)的二進(jìn)制位為01，也就是酒1為毒酒。
3. 若是乙死甲生，則對(duì)應(yīng)的二進(jìn)制位為10，也就是酒2為毒酒。
4. 若是甲乙雙死，則對(duì)應(yīng)的二進(jìn)制位為11，也就是酒3為毒酒。

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

十進(jìn)制二進(jìn)制位3二進(jìn)制位2二進(jìn)制位1酒的編號(hào)死囚丙死囚乙死囚甲00001001201030114100510161107111

同樣的，死囚所對(duì)應(yīng)的二進(jìn)制位為1，表示喝；為0，則表示不喝。

• 若死囚甲乙丙都死，則他們的二進(jìn)制位全都表示為1，也就是 111。對(duì)應(yīng)十進(jìn)制的7，也就是酒7為毒酒。
• 若死囚甲乙丙都不死，則他們的二進(jìn)制位全都表示為0，也就是 000。對(duì)應(yīng)十進(jìn)制的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。

怎么樣？感受到二進(jìn)制的神奇和美妙了嗎？

回歸數(shù)學(xué)

當(dāng)然，神奇歸神奇，那么到底為啥子可以這樣呢？為此，我還特意請(qǐng)教了一位數(shù)學(xué)專業(yè)的小學(xué)妹。她從集合的角度分析倒給了我一個(gè)全新的思考視角。

一名死囚可以表示的情況為2種：

兩名死囚可以表示的情況為4種：

三名死囚可以表示的情況為8種：

以此類推即可。

其實(shí)這個(gè)數(shù)學(xué)問題，被稱為 冪集，也就是求集合中所有的子集（包括全集和空集）構(gòu)成的集族。因?yàn)槊總€(gè)子集都有兩種情況：選，或者不選。所以，n個(gè)子集所對(duì)應(yīng)的情況為： 2的n次方，而一種情況恰好對(duì)應(yīng)著唯一的一瓶酒。是不是和之前的分析有著異曲同工之妙呢？

關(guān)于圖片：沒辦法，畫圖軟件處理不好圖層之間的關(guān)系，我就只好手畫了，哈哈。

最后

不知不覺，一篇博客就肝到了凌晨一點(diǎn)半左右：

工作以后，可以用來寫博客的時(shí)間也變少了。各位小伙伴們，如果覺得這篇博客寫的還不錯(cuò)的話，歡迎各位點(diǎn)贊、評(píng)論以及加關(guān)注哦。這樣本博主才更有動(dòng)力給大家?guī)砀嗟膬?yōu)質(zhì)博客。