這是一道非常經(jīng)典的騰訊面試題，可能對于程序猿來說并不陌生，但是對于第一次看到這道題的同學來說，確實會比較燒腦。今天除了講解這道題如何解，更多的是希望給大家引入信息論的概念，那么以后不管是遇到試毒藥還是稱球重這類問題，都是小case啦！
可能有人會說，我用100只小白鼠就可以知道毒藥是哪瓶了，所以小白鼠是招你還是惹你了，非要搭上一整個家族來給你找毒藥？其實這個問題答案很簡單，我們只需要7只小白鼠就夠了，而這個問題的解題關鍵就是數(shù)學編碼中的二進制。
一、如何用7只小白鼠找毒藥 --- 二進制編碼
Step1：我們對100個瓶子進行1～100號的編碼，再轉化為7位的二進制碼（至于為什么是7位，看到后面你就懂了）。比如1號瓶子就轉化為了“0000001”，10號瓶子就轉化為了“0001010”：
Step2：找來7只小白鼠，分別對他們進行1～7的編號。對于編號是1的小白鼠，喂它所有二進制編碼第1位（從左到右數(shù)）為1的瓶子；對于編號2的小白鼠，喂它所有二進制編碼第2位（從左到右數(shù)）為1的瓶子；以此類推...
Step3：接下來就是看一天后哪幾只老鼠掛了：如果某個編號的老鼠死了，那說明毒藥瓶子的二進制編碼在對應編號位置上的二進制值是1；反之如果某個編碼的老鼠沒有死，那說明毒藥瓶子的二進制編碼在對應編號位置上的二進制值是0。假如最后是2，3，5，7號老鼠掛了，那說明對應的毒藥瓶子二進制編碼是“0110101”，轉化成十進制，即第53號瓶子是毒藥。
二、為什么至少是7只小白鼠？--- 信息熵
前面我們只說明了7只小白鼠是可以完成找毒藥這件事情，但是我們并沒有證明7只就是最優(yōu)解，那要論證這個答案就要引入信息論中的“信息熵”這樣一個概念。
首先，我們先來了解下“熵”：
在信息論中，熵的概念和熱力學中的熵是類似的，如果大家還記得高中化學，里面有提到一個“混亂度”的概念，其實熵在熱力學里指的就是系統(tǒng)的混亂度，大概應該還記得“任何化學變化或者化學反應都是往熵增加的這個方向進行”這句話吧。
熱力學熵：系統(tǒng)的混亂程度
信息熵：信息的不確定性的度量
而在信息論中，熵指的是信息的不確定性，也就是說信息的不確定程度越大，那么對應的信息熵的也就越大，其實數(shù)學的本質就是消除信息中的這種不確定性。
對于拋硬幣來說，每次要猜正反面只能靠瞎猜，正反面出現(xiàn)的概率都是1/2，對于這類事件來說其不確定性較大，信息熵也會相對較大；如果讓你猜國足拿世界杯冠軍的可能性，那這種小概率事件的不確定性就比較小了，信息熵相對來說就會很小。
在信息論中，常用的幾個概念也可以給大家定義下，避免混淆：
信息熵：用來度量信息不確定性程度的大小，是一個絕對的值。（至于具體怎么計算度量，后面介紹）
信息：凡是在一種情況下能減少信息的不確定性的任何事物，都可以叫信息，它的反義詞可以理解為是“廢話”
信息量：是對信息的度量，表示某個具體事情發(fā)生后帶來的信息的多少，是個相對值。事件發(fā)生的概率越低，當事件發(fā)生了以后帶來的信息越大，說明信息量越大；反之越高概率事件的發(fā)生，其產生的信息量就越小。比如某明星出軌的消息被爆出來，而之前他在大眾面前的人設是個極品好男人，那么這則消息的信息量就非常大了。
接下來，回到“信息熵”如何計算度量：
信息量度量的是一個具體事件發(fā)生了所帶來的信息，而熵則是在結果出來之前對可能產生的信息量的期望——考慮該隨機變量的所有可能取值，即所有可能發(fā)生事件所帶來的信息量的期望。
所以香農給了我們一個這樣的公式（劃重點?。?/b>
P為X的概率質量函數(shù)（probability mass function），我們可以理解為事件xi 發(fā)生的概率。
b是對數(shù)所使用的底。當b = 2，熵的單位是bit。
我們用拋硬幣來舉例，“拋一次硬幣是正面”這個隨機變量X的信息熵為：
也就是“拋一次硬幣是正面”這個事件的信息熵是1 bit，我們也就只需要用1位二進制的數(shù)字即可以表示這個信息的大?。?或者1）
#開始解題# 計算小白鼠找毒藥中的信息熵：
1、首先，”100瓶藥水其中有1瓶有毒“這個隨機變量X的信息熵為：
2、1只小白鼠喝水以后的要么活著，要么死去，一共有兩種狀態(tài)，所以”1只小白鼠喝完水以后的狀態(tài)“這個隨機變量Y的信息熵為：
3、n只小白鼠喝完水會有2^n種狀態(tài)，即"n只小白鼠喝完水以后的狀態(tài)"這個隨機變量Z的信息熵為：
所以根據(jù)題目，要用到最少的老鼠來找到那瓶毒藥，轉化為信息熵就是要滿足：
H(Z)? >=? H(X)，即n >= 6.64
那么n的最小值是7，也就是說最少要7只老鼠可以找到毒藥
其實，上面的熵計算如果你覺得復雜的話，也可以這么簡化來理解：
1只小白鼠活著或者死了，可以代表兩種狀態(tài)，n只小白鼠就代表2^n種狀態(tài)
而毒藥存在1～100號瓶子中的某一瓶對應了100種情況
也就是我們需要找到最小的n滿足：
2^n?>= 100，即n>=?7
三、挑戰(zhàn)下高階版的試毒問題
仔細審題，我們發(fā)現(xiàn)這次小白鼠6小時內就會掛掉，題目沒有說具體是什么時候會掛，那我們可以理解為：喝了毒藥最久6小時會掛，如果6個小時還沒掛，說明這瓶水不是毒藥。
1、首先，還是”100瓶藥水其中有1瓶有毒“這個隨機變量X的信息熵為：
2、而這次，小白鼠的狀態(tài)有點不一樣，他在喝完水1天內的狀態(tài)可能是：
在第0分鐘的時候喝了一滴水以后，第6小時死去
第6小時依然活著，喝了一滴水以后，第12小時死去
第12小時依然活著，喝了一滴水以后，第18小時死去
第18小時依然活著，喝了一滴水以后，第24小時死去
第6小時依然活著，喝了一滴水以后，在第24小時依然活著
可見一只小白鼠在喝了一整天水后，可能會出現(xiàn)的狀態(tài)有5種，所以”1只小白鼠喝完水24h以后的狀態(tài)“這個隨機變量Y的信息熵為：
3、n只小白鼠喝了一整天水后就會有5^n種狀態(tài)，即"n只小白鼠喝完水24h以后的狀態(tài)"這個隨機變量Z的信息熵為：
所以根據(jù)題目，要用到最少的老鼠來找到那瓶毒藥，轉化為信息熵就是要滿足：
H(Z)? >=? H(X)，即 2.3219n >= 6.64
那么n的最小值是3，也就是說最少要3只老鼠可以找到毒藥
留個作業(yè)：那具體怎么利用這3只小白鼠找到毒藥呢？
根據(jù)前面簡化版本的二進制編碼方式的思路，我們是不是可以利用小白鼠的5種狀態(tài)構造一個5進制編碼方式呢？
四、我是總結
其實小白鼠試毒這個問題，第一次遇到確實會比較難下手，對于做過的人來說，可能大部分人也僅僅停留在知道用二進制編碼的方式解決，很少會有人去思考這背后的原理和邏輯的本質。
如果把問題變得再復雜點，往往大部分人就會去試，7只小白鼠不行就8只小白鼠，反正只知道用編碼的方式，這就是知其然而不知所以然。
同樣的，當我們僅僅掌握了許多理論知識，但是缺乏應用場景的實操以及面向各種情況的修正與優(yōu)化，最終也將是紙上談兵。
所以，這也是我個人比較推崇的一種思考方式：當我們遇到一個好玩的問題以及巧妙的解決方法的時候，我們可以繼續(xù)去深挖背后的原理和邏輯的本質，再反推更多的應用場景，做到舉一反三，這樣才能不斷的鍛煉自己思維能力的廣度和深度。
