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