兩篇文章，主要向大家展示了算法對(duì)于計(jì)算機(jī)來(lái)說(shuō)有多重要，多神奇，性能提升效果顯著。那二進(jìn)制算法的思路是如何形成的呢？
我們先從一道有趣的題目開(kāi)始。
有100瓶藥水，其中一瓶是毒藥，只要一小滴，就足以讓小白鼠24小時(shí)內(nèi)死亡。請(qǐng)問(wèn)怎么在1天內(nèi)用最少的老鼠找出這瓶毒藥？
先從暴力破解的方法來(lái)看，100瓶，每一瓶對(duì)應(yīng)一只小白鼠，即使用100只小白鼠可以找到那一瓶毒藥。這種解法，可以看做是將100瓶毒藥放到了一條直線的維度，因此，想要減少小白鼠的個(gè)數(shù)，很簡(jiǎn)單，提升維度即可。
第二種方法，就是將100瓶毒藥，按照橫向10，豎向10排列成一個(gè)正方形，即二維，此時(shí)只需要使用10+10只小白鼠，就可以定位出哪一個(gè)位置的是毒藥。
按照上述邏輯，想要再減少小白鼠的個(gè)數(shù)，就需要繼續(xù)升高維度，我們下面寫(xiě)一下維度與個(gè)數(shù)的關(guān)系表。
|
維度 |
100開(kāi)維度數(shù)的方根 |
個(gè)數(shù) |
|
1 |
100 |
100 |
|
2 |
10 |
10+10=20 |
|
3 |
4.64 |
5+5+4=14 |
|
4 |
3.16 |
3+3+3+4=13 |
|
5 |
2.51 |
2+2+3+3+3=13 |
|
6 |
2.15 |
2+2+2+2+3+3=14 |
|
7 |
1.93 |
2+2+2+2+2+2+2=14 |
由上面的表可以看出，并不是一直提升維度就可以減少小白鼠個(gè)數(shù)，這是因?yàn)槊吭黾右粋€(gè)維度，這個(gè)維度上至少需要兩只小白鼠，否則沒(méi)有意義，過(guò)量的維度反而會(huì)導(dǎo)致小白鼠個(gè)數(shù)的增加。
那接下來(lái)該如何思考呢？
我們換一種思路來(lái)思考這個(gè)問(wèn)題，上面我們是通過(guò)對(duì)100瓶的位置進(jìn)行升維來(lái)實(shí)現(xiàn)減少小白鼠的個(gè)數(shù)，我們?cè)購(gòu)男“资筮@一邊來(lái)進(jìn)行分析。
每一只小白鼠在喝了瓶?jī)?nèi)液體并經(jīng)過(guò)24小時(shí)后，都只有兩種狀態(tài)，死或生。n只小白鼠，狀態(tài)會(huì)有2^n種。從信息論的觀點(diǎn)來(lái)看，確定毒藥所需要的信息量H(d) = -(p1 log p1+p2 log p2+.....p100 log p100)，p1=p2=....=p100=1/100，小白鼠生死的信息量H(s) = -(p1 log p1+p2 log p2+.....p2^n log p2^n)，p1=p2=....=p2^n=1/2^n，H(s) > H(d)，即2^n > 100，n>6.64，所以至少需要7只小白鼠，才可以將那1瓶毒藥找出來(lái)。
具體方法就是將瓶子的編號(hào)1~100，用二進(jìn)制來(lái)表示，二進(jìn)制的每一位對(duì)應(yīng)一只老鼠，第一只老鼠喝二進(jìn)制編號(hào)的第一位為1的瓶子內(nèi)的液體；第二只老師喝二進(jìn)制編號(hào)的第二位為1的瓶子內(nèi)的液體；依次類推。第二天看死掉老鼠在哪一位，將所有位置1，即可查到毒藥的位置。
由此可以看出，信息論的思考方法有多么神奇。我們回到之前分析100W注彩票的問(wèn)題，彩票選號(hào)碼，實(shí)際每一個(gè)數(shù)也是只有兩種狀態(tài)，選中和未選中。我們從小白鼠的題目推演過(guò)來(lái)，1-33中選6個(gè)數(shù)，就可以用二進(jìn)制來(lái)表示，而計(jì)算機(jī)存儲(chǔ)就是用二進(jìn)制，所以這樣計(jì)算的效率非常高。
