25桶水中有壹桶有毒，豬喝水後15分鐘內就會死亡。壹小時內找到這桶毒水需要幾頭豬？
看到這個問題，我直接用了二分法。25桶直接分成12桶+12桶+1桶，然後12分鐘，6分鐘，3分鐘，1分鐘。最終計算結果是需要5頭豬，也就是說現在需要25桶水。但是我的答案是錯的...
百度了壹下，發現是個leecode話題。正確答案是2。解決方案也很好理解。在這裏，我借用百度的壹張圖來幫助我理解。如果我不明白下面的解釋，也可以看看博主原文:【leet碼】-哪壹桶水有毒？
如圖，將25桶水分成5排5列，送兩頭豬，壹頭逐排喝(註意這壹排5桶水壹次性混合)，另壹頭逐排喝。以壹排豬為例。如果他們在15分鐘後死亡，則毒水在1欄。如果他們活著，就繼續喝第二列，然後等30分鐘，45分鐘，60分鐘，看他們死不死鎖定哪壹列。如果60分鐘後他們還沒死，說明前四列沒有毒水，那麽通過排除法就可以知道毒水只能在第五列。同理，只要最後鎖定了行數和列數，交集壹定是毒水所在的地方。
可以觀察到，這個解的關鍵是壹頭豬充分利用了15分鐘的間隔，在1小時內直接識別出五桶水(實際上是五桶混合水)是否有毒。如果題目換成10分鐘的區間，那麽1小時可以識別出7桶水。這個時候7的2次方是49，還需要2頭豬。
進壹步展開，間隔依然是15分鐘，但總* * *是1000桶水？其實壹頭豬只能分辨5，兩個維度只能是5乘以5，然後壹個是5的三次方；很容易發現問題其實變成了多少次才能找到5可以大於1000，簡單的答案就是5頭豬。其實這個時候5的五次方就是3125，也就是說就算是3000桶水，五頭豬也夠了。
讓我們展開它。如果間隔是15分鐘，但要求是15分鐘，而不是壹個小時怎麽辦？這時會發現，15分鐘後，豬只有兩種狀態，要麽死，要麽活。即每排或每列實際上只能放2桶水。那麽問題就變成了2的多少次方大於25。嗯，這個時候的答案和我剛開始用的二分法壹模壹樣。這時候我才明白，我的二分法其實不用1小時，只需要15分鐘就能鑒別出毒水。因為題目說每桶水有無限量，我可以先按照二分法的思路把25桶水全部拆了，然後下壹個命令，5頭豬同時上去喝對應的組，當然要15分鐘我才知道結果。
然而，直到現在，事情才剛剛開始...比如這個知乎三萬贊回答:
1000桶水，其中壹桶有毒。豬喝了毒水會在15分鐘內死亡。壹小時內找到這桶毒水需要幾頭豬？——苗華東的回答。-知乎
作者拋出了信息熵的定義和公式:
然後用這個公式計算，顯得我很蠢。這裏建議先通過其他鏈接補充基礎知識。
什麽是參考信息熵？——運籌學的答案。-知乎
信息熵，信息熵，妳怎麽看？如果“熵”這個詞不順眼，那就先別看。至少我們知道這個概念和信息有關。而且是數學模型中的概念，壹般可以量化。那麽，第壹個問題來了:信息可以量化嗎？
至少直覺上是可能的。不然怎麽會認為有的人廢話連篇，“沒有信息”，有的人壹針見血，壹句話就傳達了很多信息？
有些事情不確定，比如明天股票會漲還是會跌。如果妳告訴我NBA總決賽明天開打，這兩者好像沒什麽關系，那麽妳的信息帶來的關於明天股票是漲是跌的信息很少。但如果在NBA總決賽開始的時候，大家都不再關註股票，有99%的幾率股票會跌，那麽妳的這句話就很有參考價值了，因為原本不確定的事情變得非常確定。
而有些事情已經很確定了，比如太陽從東方升起。如果妳告訴我太陽從東方升起壹百次，妳的話還是壹點信息都沒有，因為這件事不能再確定了。
所以信息量與不確定性的變化有關。
第壹，與事物可能結果的數量有關；第二，跟概率有關。
先說壹個。例如，我們討論太陽從哪裏升起。結果只有壹個，我們早就知道，無論誰傳遞任何信息，都是沒有信息的。當可能結果的數量相對較多時，我們得到的新信息就有可能擁有大量的信息。
第二，可能結果的數量不夠，還要看初始概率分布。比如我壹開始就知道小明在電影院15*15座位的A廳看電影。小明燦坐的座位有225個，這可能會導致座位過多。但是，如果我們壹開始就知道小明坐在第壹排最左邊的可能性是99%，坐在其他位置的可能性很小，那麽在大多數情況下，妳再告訴我小明的任何信息都沒有多大用處，因為我們幾乎可以確定小明坐在第壹排最左邊。那麽，如何衡量不確定性的變化呢？怎麽定義？這個問題不好回答，但是如果我們已經知道這個量已經存在了，我們不妨稱之為信息量，那麽妳認為信息量至少應該滿足什麽特征呢？
什麽函數能滿足以上四個條件？
負對數函數，也就是-log(x)！取大於1的基數，確保此函數非負。把前面乘以壹個正常的數就行了。
A.為什麽不是正面的？因為如果是正數，因為x是小於等於1的數，log(x)小於等於0。滿足第壹個特征。
b .讓我們驗證其他功能。第三種最容易。如果x是壹個概率，那麽log(x)連續依賴於x .
四個怎麽樣？如果有n個可能的結果，任何壹個的概率都是1/n，-log(1/n)是n的增函數，沒問題。
d .最後驗證二。因為-log(xy) = -log(x) -log(y)，所以也是正確的。學數學的同學要註意，這裏的y可以是給定X的條件概率，當然也可以獨立於X，對了，這個函數是唯壹的(除了可以乘以任意常數)。妳可以自己證明或者有時間查查書。
好，那麽我們知道，壹個事件的信息量是這個事件概率的負對數。最後，我們可以回到信息熵。信息熵與所有的可能性有關。每壹個可能的事件都有概率。信息熵是事件發生時我們獲得的平均信息量。所以從數學上來說，信息熵其實就是對信息的期望。(表情見其他答案或見下文)
什麽是參考信息熵？-D .韓的回答。-知乎
賭馬比賽有四匹馬{A，B，C，D}，獲勝概率為{1/2，1/4，1/8，1/8}。接下來，我們把哪匹馬贏看成隨機變量x。
假設我們需要用盡可能少的二元問題來確定隨機變量x的值，比如問題1: A贏了嗎？問題2:B贏了嗎？問題3:C贏了嗎？最後，我們可以通過多達三個二元問題來確定X的值，即哪匹馬贏得了比賽。
那麽就很容易計算，這樣，就可以確定x的值。
當我們使用上面的信息熵公式時，它是這樣的:
-1/2 * log(1/2)+-1/4 * log(1/4)+-1/8 * log(1/8)+-1/8 * log(1/8)
這裏很容易計算出結果，比如:-1/2 * log(1/2)=-1/2 *(log 1-log2)= 1/2 * log2 = 1/2。
1/2+1/2+3/8+3/8 = 7/4
可以發現信息熵公式的計算結果與前面的計算是壹致的。在二進制計算機中，壹位是0或1，實際上代表了壹個二進制問題的答案。也就是說，在計算機中，我們需要1.75位的平均碼長來編碼哪匹馬獲得了冠軍。
顯然，為了盡可能地減少代碼長度，我們應該為概率較高的事件分配較短的代碼長度。經過對這個問題的深入討論，我們可以得到霍夫曼編碼的概念。
延伸閱讀請參考H264系列九熱力學熵信息熵霍夫曼編碼哥倫布編碼。在這篇文章中，還有壹個非常有趣的例子:
我要擲骰子壹次。在觀察結果之前，骰子的六個面都有可能，概率完全壹樣(都是1/6)。此時，該事件的信息熵為。這個結果用前面的信息熵公式也計算得很好，相當於累加-1/6 * log(1/6)6次，即，-log(1/6)=-(log 1-log 6)= log6。註意，這個算法後面會用來計算豬什麽時候喝了毒水。
現在全能女神給了我壹個提示，這個骰子的結果壹定是偶數，所以可能的結果從6個減少到3個，事件的熵就變成了。換句話說，當我被提示時，對事件結果的不確定性就減少了。我們將信息熵約減的量定義為信息量I，上面提示中的信息量正好是1比特，相當於對壹個完全未知的命題做出是非判斷所需的信息量。而如果我想得到唯壹確定的結果，P(x)必須等於1，此時的信息熵為零。我們需要的信息是原始熵。
看到這裏，妳壹定也能自己總結出另壹個閃閃發光的結論:信息是負熵的。需要註意的是，這句話中的“熵”指且僅指信息熵。試圖將這壹結論推廣到對熱力學熵的解釋，往往缺乏足夠的事實依據，意義也往往模棱兩可。
是時候回到知乎的30000贊了:1000桶水，其中壹桶有毒，豬喝了毒水會在15分鐘內死亡。壹小時內找到這桶毒水需要幾頭豬？——苗華東的回答。-知乎
1000桶水，其中壹桶有毒。豬喝了毒水會在15分鐘內死亡。15分鐘找到這桶毒水需要幾頭豬？
首先，隨機變量X的信息熵是:-(1/1000)* log(1/1000)累計1000次。這個很好理解。任何桶裏出現毒水都是等概率事件。累積的結果是:
-log(1/1000)= log 1000約為9.966。
1頭豬喝水後不是活著就是死了，壹個* * *，有兩種狀態，那麽“1頭豬喝水後”的隨機變量Y的信息熵為
N頭豬喝水後會有2個N次方狀態，即隨機變量Y的信息熵為“N頭豬喝水後的狀態”
所以根據題目要求，如果至少需要N頭豬才能找到這桶毒水，那麽隨機變量Y的信息熵壹定大於隨機變量X的信息熵，即H (y) >: = H(X)，即N >；= 9.966，即n = 10
當我們用信息熵計算n的最小值時，我們可以堅信n=10壹定是理論上的最優解，試圖尋找壹個小於10的值是徒勞的。
其實上面信息熵計算的簡化版可以寫成下面更好理解的形式，也可以解為n = 10。形式雖然簡單，但是壹定要記住背後的原理是信息熵。
至於采用什麽方案，就涉及到技術層面了。就算暫時想不出來，我們也會有努力的方向，會知道努力的邊界在哪裏，不會去做找永動機之類的事情。
1000桶水，其中壹桶有毒。豬喝了毒水會在15分鐘內死亡。壹小時內找到這桶毒水需要幾頭豬？
1000桶水中有壹桶有毒，和第壹個問題壹樣，還是9.966。但是，豬的信息熵不壹樣。我們可以想象壹頭豬在壹個小時內會有多少種狀態。
可以看出，1豬在1小時後會有五種狀態，所以“1豬在1小時後”的隨機變量Z的信息熵為
1小時後，N頭豬會有5個N次方狀態，即隨機變量Y的信息熵為“1小時後N頭豬的狀態”
所以根據題目要求，如果至少需要N頭豬才能找到這桶毒水，那麽隨機變量Y的信息熵必須大於隨機變量。
量x的信息熵，即h(y)>；= H(X)，即n >；= 9.966/2.3219 = 4.292，即n = 5
事實上，對於n = 5，不僅檢測1000桶水，甚至檢測3000桶水都沒有問題。感興趣的童鞋
妳可以試著計算壹下
在這壹點上，香農給了我們壹個理論上的極限，但具體的方案還是需要我們自己去構造。n=5由我們決定。
理論基礎，並畫出具體的計劃是我們的工程水平。
還是知乎三萬贊的作者，參考香農的信息論，牛在哪裏？-苗華東的回答-知乎，老習慣，這裏只介紹思路，具體方案看作者原文。
外觀相同的12球中有1壞球，其重量比其他11好球輕。現在有壹個沒有重量的天平。妳至少要稱幾次才能確定找到這個壞球？
我們可以想壹想，稱1次的天平會有三種結果:
因此，隨機變量z“天平稱1次後的結果”的信息熵為
如果將上述公式簡化，即
外觀相同的12球中有1壞球，其重量與其他11球不同。現在有壹個沒有重量的天平。妳至少要稱幾次才能確定找到這個壞球？
這個問題和上壹個問題的區別在於，我們不知道壞球的重量。這與之前已知的壞球是光相比對信息熵有什麽影響？
如果天平的兩邊都有兩個球。如果知道壞球比較輕，我可以馬上知道天空不平衡時壞球是比較輕的那壹面。當我不知道壞球是輕還是重的時候，如果天平不平衡，我就無法判斷壞球是重還是輕。我只能知道壞球是輕還是重。所以，當我們不知道壞球是輕是重的時候，我們每次測量壞球的時候，都存在壹個壞球是輕是重的不確定性。在上面問題的基礎上，在最高的位置加壹個數字表示球的重量。其中0表示輕，1表示重，如下表所示。所以雖然有12個球，但是因為重量的不確定性，所以有24種狀態。
所以隨機變量X“確定1個外觀相同的球”的信息熵為
但是隨機變量Y“稱了n次天平的結果”的信息熵沒有變化，因為天平壹次只能確定三種狀態，所以
同理，h (y) >: = H(X)，即n >；= 2.893，也就是n = 3，可以看出上壹題沒有充分發揮天平的信息優勢，仍然可以檢測出三次粗心的壞球。這就是用理論武裝頭腦的好處，先找到答案，再思考方案。這種自上而下的思考方式的好處是，在思考計劃之前，我們有壹個目標和工作的方向，而不是像壹只無頭蒼蠅。
如果妳看了文章開頭標題為“用1000桶水找毒藥”的童鞋，妳可能會發現解決這個問題的思路和解決那個問題的思路幾乎是壹樣的。雖然表面上看是壹類不同的問題，但我們要向香櫞的老祖宗學習，透過問題的表象，直達本質。
這兩個話題的底層邏輯是信息熵。在我們掌握理論工具的時候，人與人的差距就在於我們是否有足夠的能力把現實問題抽象成數學或者其他問題，然後用我們熟悉的理論工具去解決。在這壹點上，沈降方程是相同的。解方程本身很簡單，難點是如何把真題抽象成表達式，定義變量，列出方程。關於這壹點的詳細陳述在我的另壹篇文章《數學思維在生活中有多大用處？中有更詳細的描述。
參考1000桶水，其中壹桶有毒。豬喝了毒水會在15分鐘內死亡。壹小時內找到這桶毒水需要幾頭豬？——普蘭格爾的回答。-知乎
考慮這個過程:假設給妳兩個數字A和B，只允許妳比較壹次，把兩個數字從小到大排序。妳不覺得這個問題很簡單嗎？這兩個數字只要比較壹次，數字最小的排第壹。
我們來分析壹下這個看似簡單的問題的本質。
如果只能比較壹次，那麽根據這種比較，我們實際上只能得到兩種信息:要麽第壹個數更小，要麽第二個數更小。而兩個數從小到大的關系只有兩種情況:要麽a，b，要麽b，a，也就是說，我們可以基於這個比較的結果建立壹個結果-最終排列雙射關系，每次比較的結果都唯壹對應最終的大小關系。
現在考慮上述問題的升級版:如果給妳A、B、C、D四個數字，妳能通過四次比較把它們從小到大排序嗎？答案是否定的，因為我們通過四次比對所能得到的信息最多只有2的四次方，也就是16種。而這四個數字的排列* * *有四個！=24種。因此，不可能將查詢的結果與最終的排列壹壹對應，我們證明4不可能是答案的下界。
我們再升級壹下，考慮n個數排序的情況。如果我們在最終方案中使用k次比較，那麽可能的信息是2的k次方，n個數的排列是n！善良。為了在結果和最終排列之間建立雙射關系，必須滿足以下要求:
現在我們從信息論的角度來思考原問題。1000桶水，只有壹桶有毒，換句話說，只有1000個可能的答案。
每頭豬在中毒後的15分鐘內死亡，那麽我們可以從每頭豬身上得到五種信息:在[0，15] [15，30] [30，45] [45，60]的哪個時間段，它死亡或最終存活。如果最後有K頭豬，我們可以得到的信息有幾種，換句話說，需要滿足K，也就是K的下界是5。