題目：1000瓶毒藥中只有一瓶有毒，獨(dú)發(fā)時(shí)間為24小時(shí)，有多少老鼠在24小時(shí)后詢問該病是否有毒。

思路：這題試Bloom Fliter 算法。詳情可以參考：

這題和我之前看到的一道題有點(diǎn)像。題為，

有1000個(gè)蘋果，分別裝在10個(gè)箱子里，任意給出1到1000之間的整數(shù)，都可以利用某幾個(gè)箱子中的蘋果數(shù)量獲得次數(shù)。

2^10 =1024 。也就是說10層二叉樹一定可以記錄1000種的狀態(tài)。每個(gè)節(jié)點(diǎn)放1，每一層的和就是一個(gè)數(shù)。

所以數(shù)分別為1 ， 2 ，4 ，8，16, 32,64,128,256,489。（489=488+1，因?yàn)榭倲?shù)為1000）。

我們能表示出1024種狀態(tài)。

這個(gè)題是對(duì)bit位的應(yīng)用，1000接近1024，所以需要10個(gè)bit位，對(duì)瓶子進(jìn)行編號(hào)，從0到999，這樣需要10只老鼠。瓶子的編號(hào)分別為：

老鼠用 a ,b ,c ,d ,e ,f ,g ,h ,i , j ,表示

第0號(hào)瓶：00000,00000

第1號(hào)瓶：00000,00001 a

第2號(hào)瓶：00000,00010, b

第3號(hào)瓶：00000,00011 a b

第4號(hào)瓶：00000,00101 a c

第5號(hào)瓶：00000,00111 a b c

。。。。。。

第999號(hào)瓶：11111，00111 a b c [] [] f g h i j

同時(shí)給老鼠編號(hào)，從1,2,...10，從低位開始，讓第n個(gè)老鼠喝下第n個(gè)bit位為1瓶子中的藥水。一周后，若所有的老鼠都沒有發(fā)病，那么是第一個(gè)瓶子有毒，如果有一些老鼠發(fā)病，那么共同喝的那瓶毒藥的二進(jìn)制做與運(yùn)算，得到的就是共同喝的那瓶，最低位+1，變成整數(shù)后，對(duì)應(yīng)的數(shù)字即為有毒藥水的編號(hào)。

比如：第四瓶有毒，全部做與運(yùn)算得到的（編號(hào)第三號(hào)）00000011 +1 =00000100 = 4 。第四瓶有毒（沒有第零瓶，所以+加1）

所以只要10只老鼠就能在 24小時(shí)后 排查出到底那瓶有毒。

還可以用二分法解決：

第一次： 將1-500瓶兌在一起喝。

如果老鼠死了，則拿另一只老鼠去品嘗501-725瓶兌的藥水。否則去喝2-250瓶兌的水。

采用如此二分法，因?yàn)?^10>1000 2^9<1000,所以10次就可以找出。

現(xiàn)在回到原題，老鼠會(huì)在24小時(shí)后死亡，這樣的化就不能跟去前一次的結(jié)果作出決策。但是可以覆蓋二分的所有支路，在24小時(shí)后，一次性作出判斷。

相當(dāng)于將串行的二分法，改為并行的二分法。

具體如下：

第一只： 喝 1-500

第二只 1-250 500-725

第三只 1-125 250-375 500-625 725-850

....

到最后中毒的可以通過交叉中毒分析出是那瓶。這個(gè)其實(shí)和Bloomfliter算法思想很像。也是一只老鼠喝多瓶藥水與其他老鼠部分相交而且與每只相交的部分還不一樣。當(dāng)老鼠達(dá)到一定數(shù)量，就能過濾出到底那瓶有毒了。