起點(diǎn)課堂會(huì)員權(quán)益
職業(yè)體系課特權(quán)
線(xiàn)下行業(yè)大會(huì)特權(quán)
個(gè)人IP打造特權(quán)
30+門(mén)專(zhuān)項(xiàng)技能課
1300+專(zhuān)題課程
12場(chǎng)職場(chǎng)軟技能直播
12場(chǎng)求職輔導(dǎo)直播
12場(chǎng)專(zhuān)業(yè)技能直播
會(huì)員專(zhuān)屬社群
榮耀標(biāo)識(shí)經(jīng)典騰訊面試題：小白鼠試毒問(wèn)題
編輯導(dǎo)讀：有100瓶藥水，其中一瓶是毒藥，只要一小滴，就足以讓小白鼠24小時(shí)內(nèi)死亡。請(qǐng)問(wèn)怎么在1天內(nèi)用最少的老鼠找出這瓶毒藥？本文作者對(duì)此進(jìn)行了解答，一起來(lái)看看吧。
這是一道非常經(jīng)典的騰訊面試題，可能對(duì)于程序猿來(lái)說(shuō)并不陌生，但是對(duì)于第一次看到這道題的同學(xué)來(lái)說(shuō)，確實(shí)會(huì)比較燒腦。今天除了講解這道題如何解，更多的是希望給大家引入信息論的概念，那么以后不管是遇到試毒藥還是稱(chēng)球重這類(lèi)問(wèn)題，都是小case啦！
可能有人會(huì)說(shuō)，我用100只小白鼠就可以知道毒藥是哪瓶了，所以小白鼠是招你還是惹你了，非要搭上一整個(gè)家族來(lái)給你找毒藥？其實(shí)這個(gè)問(wèn)題答案很簡(jiǎn)單，我們只需要7只小白鼠就夠了，而這個(gè)問(wèn)題的解題關(guān)鍵就是數(shù)學(xué)編碼中的二進(jìn)制。
一、如何用7只小白鼠找毒藥 — 二進(jìn)制編碼
Step1：我們對(duì)100個(gè)瓶子進(jìn)行1～100號(hào)的編碼，再轉(zhuǎn)化為7位的二進(jìn)制碼（至于為什么是7位，看到后面你就懂了）。比如1號(hào)瓶子就轉(zhuǎn)化為了“0000001”，10號(hào)瓶子就轉(zhuǎn)化為了“0001010”：
Step2：找來(lái)7只小白鼠，分別對(duì)他們進(jìn)行1～7的編號(hào)。對(duì)于編號(hào)是1的小白鼠，喂它所有二進(jìn)制編碼第1位（從左到右數(shù)）為1的瓶子；對(duì)于編號(hào)2的小白鼠，喂它所有二進(jìn)制編碼第2位（從左到右數(shù)）為1的瓶子；以此類(lèi)推…
Step3：接下來(lái)就是看一天后哪幾只老鼠掛了：如果某個(gè)編號(hào)的老鼠死了，那說(shuō)明毒藥瓶子的二進(jìn)制編碼在對(duì)應(yīng)編號(hào)位置上的二進(jìn)制值是1；反之如果某個(gè)編碼的老鼠沒(méi)有死，那說(shuō)明毒藥瓶子的二進(jìn)制編碼在對(duì)應(yīng)編號(hào)位置上的二進(jìn)制值是0。假如最后是2，3，5，7號(hào)老鼠掛了，那說(shuō)明對(duì)應(yīng)的毒藥瓶子二進(jìn)制編碼是“0110101”，轉(zhuǎn)化成十進(jìn)制，即第53號(hào)瓶子是毒藥。
二、為什么至少是7只小白鼠？— 信息熵
前面我們只說(shuō)明了7只小白鼠是可以完成找毒藥這件事情，但是我們并沒(méi)有證明7只就是最優(yōu)解，那要論證這個(gè)答案就要引入信息論中的“信息熵”這樣一個(gè)概念。
首先，我們先來(lái)了解下“熵”：
在信息論中，熵的概念和熱力學(xué)中的熵是類(lèi)似的，如果大家還記得高中化學(xué)，里面有提到一個(gè)“混亂度”的概念，其實(shí)熵在熱力學(xué)里指的就是系統(tǒng)的混亂度，大概應(yīng)該還記得“任何化學(xué)變化或者化學(xué)反應(yīng)都是往熵增加的這個(gè)方向進(jìn)行”這句話(huà)吧。
熱力學(xué)熵：系統(tǒng)的混亂程度
信息熵：信息的不確定性的度量
而在信息論中，熵指的是信息的不確定性，也就是說(shuō)信息的不確定程度越大，那么對(duì)應(yīng)的信息熵的也就越大，其實(shí)數(shù)學(xué)的本質(zhì)就是消除信息中的這種不確定性。
對(duì)于拋硬幣來(lái)說(shuō)，每次要猜正反面只能靠瞎猜，正反面出現(xiàn)的概率都是1/2，對(duì)于這類(lèi)事件來(lái)說(shuō)其不確定性較大，信息熵也會(huì)相對(duì)較大；如果讓你猜國(guó)足拿世界杯冠軍的可能性，那這種小概率事件的不確定性就比較小了，信息熵相對(duì)來(lái)說(shuō)就會(huì)很小。
在信息論中，常用的幾個(gè)概念也可以給大家定義下，避免混淆：
1、信息熵：用來(lái)度量信息不確定性程度的大小，是一個(gè)絕對(duì)的值。（至于具體怎么計(jì)算度量，后面介紹）
2、信息：凡是在一種情況下能減少信息的不確定性的任何事物，都可以叫信息，它的反義詞可以理解為是“廢話(huà)”
3、信息量：是對(duì)信息的度量，表示某個(gè)具體事情發(fā)生后帶來(lái)的信息的多少，是個(gè)相對(duì)值。事件發(fā)生的概率越低，當(dāng)事件發(fā)生了以后帶來(lái)的信息越大，說(shuō)明信息量越大；反之越高概率事件的發(fā)生，其產(chǎn)生的信息量就越小。比如某明星出軌的消息被爆出來(lái)，而之前他在大眾面前的人設(shè)是個(gè)極品好男人，那么這則消息的信息量就非常大了。
接下來(lái)，回到“信息熵”如何計(jì)算度量：
信息量度量的是一個(gè)具體事件發(fā)生了所帶來(lái)的信息，而熵則是在結(jié)果出來(lái)之前對(duì)可能產(chǎn)生的信息量的期望——考慮該隨機(jī)變量的所有可能取值，即所有可能發(fā)生事件所帶來(lái)的信息量的期望。
所以香農(nóng)給了我們一個(gè)這樣的公式（劃重點(diǎn)?。?/strong>
P為X的概率質(zhì)量函數(shù)（probability mass function），我們可以理解為事件xi 發(fā)生的概率。
b是對(duì)數(shù)所使用的底。當(dāng)b = 2，熵的單位是bit。
我們用拋硬幣來(lái)舉例，“拋一次硬幣是正面”這個(gè)隨機(jī)變量X的信息熵為
也就是“拋一次硬幣是正面”?這個(gè)事件的信息熵是1 bit，我們也就只需要用1位二進(jìn)制的數(shù)字即可以表示這個(gè)信息的大?。?或者1）
#開(kāi)始解題# 計(jì)算小白鼠找毒藥中的信息熵：
1、首先，”100瓶藥水其中有1瓶有毒“這個(gè)隨機(jī)變量X的信息熵為：
2、1只小白鼠喝水以后的要么活著，要么死去，一共有兩種狀態(tài)，所以”1只小白鼠喝完水以后的狀態(tài)“這個(gè)隨機(jī)變量Y的信息熵為：
3、n只小白鼠喝完水會(huì)有2^n種狀態(tài)，即”n只小白鼠喝完水以后的狀態(tài)”這個(gè)隨機(jī)變量Z的信息熵為：
所以根據(jù)題目，要用到最少的老鼠來(lái)找到那瓶毒藥，轉(zhuǎn)化為信息熵就是要滿(mǎn)足：
H(Z) >= H(X)，即n >= 6.64
那么n的最小值是7，也就是說(shuō)最少要7只老鼠可以找到毒藥
其實(shí)，上面的熵計(jì)算如果你覺(jué)得復(fù)雜的話(huà)，也可以這么簡(jiǎn)化來(lái)理解：
1只小白鼠活著或者死了，可以代表兩種狀態(tài)，n只小白鼠就代表2^n種狀態(tài)
而毒藥存在1～100號(hào)瓶子中的某一瓶對(duì)應(yīng)了100種情況
也就是我們需要找到最小的n滿(mǎn)足：
2^n>= 100，即n>=7
三、挑戰(zhàn)下高階版的試毒問(wèn)題
仔細(xì)審題，我們發(fā)現(xiàn)這次小白鼠6小時(shí)內(nèi)就會(huì)掛掉，題目沒(méi)有說(shuō)具體是什么時(shí)候會(huì)掛，那我們可以理解為：喝了毒藥最久6小時(shí)會(huì)掛，如果6個(gè)小時(shí)還沒(méi)掛，說(shuō)明這瓶水不是毒藥。
1、首先，還是”100瓶藥水其中有1瓶有毒“這個(gè)隨機(jī)變量X的信息熵為：
2、而這次，小白鼠的狀態(tài)有點(diǎn)不一樣，他在喝完水1天內(nèi)的狀態(tài)可能是：
1）在第0分鐘的時(shí)候喝了一滴水以后，第6小時(shí)死去
2）第6小時(shí)依然活著，喝了一滴水以后，第12小時(shí)死去
3）第12小時(shí)依然活著，喝了一滴水以后，第18小時(shí)死去
4）第18小時(shí)依然活著，喝了一滴水以后，第24小時(shí)死去
5）第6小時(shí)依然活著，喝了一滴水以后，在第24小時(shí)依然活著
可見(jiàn)一只小白鼠在喝了一整天水后，可能會(huì)出現(xiàn)的狀態(tài)有5種，所以”1只小白鼠喝完水24h以后的狀態(tài)“這個(gè)隨機(jī)變量Y的信息熵為：
3、n只小白鼠喝了一整天水后就會(huì)有5^n種狀態(tài)，即”n只小白鼠喝完水24h以后的狀態(tài)”這個(gè)隨機(jī)變量Z的信息熵為：
所以根據(jù)題目，要用到最少的老鼠來(lái)找到那瓶毒藥，轉(zhuǎn)化為信息熵就是要滿(mǎn)足：
H(Z) >= H(X)，即 2.3219n >= 6.64
那么n的最小值是3，也就是說(shuō)最少要3只老鼠可以找到毒藥
留個(gè)作業(yè)：那具體怎么利用這3只小白鼠找到毒藥呢？
根據(jù)前面簡(jiǎn)化版本的二進(jìn)制編碼方式的思路，我們是不是可以利用小白鼠的5種狀態(tài)構(gòu)造一個(gè)5進(jìn)制編碼方式呢？
四、我是總結(jié)
其實(shí)小白鼠試毒這個(gè)問(wèn)題，第一次遇到確實(shí)會(huì)比較難下手，對(duì)于做過(guò)的人來(lái)說(shuō)，可能大部分人也僅僅停留在知道用二進(jìn)制編碼的方式解決，很少會(huì)有人去思考這背后的原理和邏輯的本質(zhì)。
如果把問(wèn)題變得再?gòu)?fù)雜點(diǎn)，往往大部分人就會(huì)去試，7只小白鼠不行就8只小白鼠，反正只知道用編碼的方式，這就是知其然而不知所以然。同樣的，當(dāng)我們僅僅掌握了許多理論知識(shí)，但是缺乏應(yīng)用場(chǎng)景的實(shí)操以及面向各種情況的修正與優(yōu)化，最終也將是紙上談兵。
所以，這也是我個(gè)人比較推崇的一種思考方式：當(dāng)我們遇到一個(gè)好玩的問(wèn)題以及巧妙的解決方法的時(shí)候，我們可以繼續(xù)去深挖背后的原理和邏輯的本質(zhì)，再反推更多的應(yīng)用場(chǎng)景，做到舉一反三，這樣才能不斷的鍛煉自己思維能力的廣度和深度。
本文由 @WINTER 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載
題圖來(lái)自Pexels，基于CC0協(xié)議
核酸混檢法可以嗎？
33+33+34，測(cè)試第1次，用三只，死一只
11/12+11+11，測(cè)試第二次，補(bǔ)一只，用三只，死一只
3/4+3/4+3/4，測(cè)試第三次，補(bǔ)一只，用三或四只，死一只
1+1+1+1，測(cè)試第四次，補(bǔ)一只，用三或四只，死一只，確認(rèn)
共測(cè)試4次，用7只老鼠，死4只
小鼠中毒會(huì)在24小時(shí)內(nèi)死亡，但題目要求一天內(nèi)查出毒藥。時(shí)間不夠二次檢驗(yàn)的。
核酸混檢法可以嗎
第一種最多6種，不可能同時(shí)出現(xiàn)1111111的狀態(tài)，最多有6個(gè)1
6個(gè)1最多只能表示64個(gè)狀態(tài)哦兄弟
有個(gè)疑問(wèn)：為啥算小鼠生或死的時(shí)候，兩種狀態(tài)的概率都是 1/2？這里為啥不需要考慮這 100 瓶里具體有多少瓶毒藥？
好問(wèn)題哦，因?yàn)檫@里算的是熵值，代表的是信息的不確定性，一般我們會(huì)取最最大值（也就是最不確定的情況，信息到底有多混亂，所以也就不考慮他喝多水里只有1%的概率會(huì)死了
啊~長(zhǎng)知識(shí)了，還以為是人格測(cè)試題，原來(lái)就是個(gè)單純的題
其實(shí)用來(lái)解讀人格也不是不行
看見(jiàn)這個(gè)問(wèn)題真的讓我迷迷糊糊的哈哈哈，解釋的很清晰！
100只小白鼠最后只會(huì)死一只，七只小白鼠有可能會(huì)死好幾只。。。
最少死七只小白鼠
至多死6只
真愛(ài)小動(dòng)物 真愛(ài)生命
你還是挺善良的！