資源描述：
《用信息論構(gòu)造出稱(chēng)球問(wèn)題的解.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、用信息論構(gòu)造出稱(chēng)球問(wèn)題的解趙明達(dá)提要：本文用信息論推導(dǎo)出稱(chēng)球問(wèn)題的解，并構(gòu)造了的遞推操作的稱(chēng)量辦法，徹底解決了任意個(gè)球的稱(chēng)球問(wèn)題。關(guān)鍵詞：稱(chēng)量信息量概率遞推經(jīng)典的稱(chēng)球題目是這樣的：“十二個(gè)外表相同的球中有一個(gè)壞球，它的重量和其它十一個(gè)好球不同，現(xiàn)在有一臺(tái)沒(méi)有砝碼的天平，問(wèn)需要稱(chēng)幾次就能確保找出那個(gè)壞球”（一）十二個(gè)球稱(chēng)幾次做過(guò)這道題目的人知道，答案是3次。不是太難，我們用圖論中的策略樹(shù)將稱(chēng)法記錄如下：稱(chēng)3次，從12個(gè)球里找到壞球，并知道壞球的輕重：
2、--右--(1輕)
3、--右--(1;2)
4、--平--(8
5、重)
6、
7、--左--(2輕)
8、
9、
10、--右--(6重)
11、--右--(1,2,7;
12、--平--(5;6)
13、--平--(4輕)
14、3,8,9)
15、
16、--左--(5重)
17、
18、
19、
20、
21、--右--(3輕)
22、
23、--左--(3;9)
24、--平--(7重)
25、
26、--左--(×)
27、
28、
29、--右--(9輕)
30、
31、--右--(9;10)
32、--平--(11重)
33、
34、
35、--左--(10輕)
36、
37、
38、
39、
40、--右--(12重)(1-4;5-8)
41、--平--(9-10;
42、--平--(1;12)
43、--平--(13輕,13重)*
44、11，1)
45、
46、--左--(12輕)
47、
48、
49、
50、
51、
52、--右--(10重)
53、
54、--左--(9;10)
55、--平--(11輕)
56、
57、--左--(9重)
58、
59、
60、--右--(×)
61、
62、--右--(3;9)
63、--平--(7輕)
64、
65、
66、--左--(3重)
67、
68、
69、
70、
71、--右--(5輕)
72、--左--(1,2,7;
73、--平--(5;6)
74、--平--(4重)3,8,9)
75、
76、--左--(6輕)
77、
78、
79、--右--(2重)
80、--左--(1;2)
81、--平--(8輕)
82、--左--(1重)說(shuō)明：1、*號(hào)所在的一行對(duì)應(yīng)十三個(gè)球的情形，留待后面分析13個(gè)球的時(shí)候使用，現(xiàn)在可以不管。2、樹(shù)的每一處分
83、叉就是一次稱(chēng)量，它有三個(gè)分支，分別標(biāo)注了“右”、“平”和“左”，表示稱(chēng)量的結(jié)果為“右重”、“平衡”和“左重”。3、(1,2,3,4;5,6,7,8)或者(1-4;5-8)表示“將1-4號(hào)放在左邊，5-8號(hào)放在右邊”這樣的一次“稱(chēng)量”。無(wú)疑，天平兩端球數(shù)不等時(shí)的稱(chēng)量沒(méi)有意義。4、(1重)和(2輕)表示“1號(hào)是壞球，且較重，其他球都正常”和“2號(hào)是壞球，且較輕，其他球都正?！钡淖罱K結(jié)果；可以看出，在到達(dá)最終結(jié)果前經(jīng)過(guò)了幾個(gè)分叉，便是稱(chēng)量的次數(shù)。這個(gè)結(jié)果是反復(fù)嘗試得到的，雖然直覺(jué)上三次應(yīng)該是最低了，但我們終究不
84、能百分之百的確定，我們還是會(huì)問(wèn)，兩次能搞定嗎？或者我們想，十三個(gè)球里面找一個(gè)壞球，三次可以嗎？十四個(gè)呢？……，或者問(wèn)，十個(gè)球里面找一個(gè)壞球要幾次呢？二十個(gè)、四十個(gè)呢？N個(gè)呢？……還有，稱(chēng)三次最多可以從幾個(gè)球里找到唯一的那個(gè)壞球？四次呢？五次、六次呢？M次呢？解這樣的題目有規(guī)律可循嗎？一般的，我們要解決以下問(wèn)題：給定任一自然數(shù)N，⑴找出N個(gè)球稱(chēng)球問(wèn)題所需的最小稱(chēng)量次數(shù)；⑵給出最小次數(shù)稱(chēng)球的具體方法。這道題的解決無(wú)非是要獲得“十二個(gè)球中哪一個(gè)球是壞球的”的信息，是要確定一個(gè)事件集合里最終哪一個(gè)事件發(fā)生的過(guò)程。
85、下面，我們用信息論的幾個(gè)基本原理，試著分析一下。（隨便找一本介紹有關(guān)香農(nóng)信息論的書(shū)，都會(huì)有下面的內(nèi)容，對(duì)信息論有所了解的，可以跳過(guò)下面一段）香農(nóng)在他創(chuàng)立的信息論中，將信息定義為對(duì)“事物不確定性的消除”，消除了多少不確定性，用信息量來(lái)衡量。一個(gè)事件集合中究竟發(fā)生哪一件事情就是不確定的，每個(gè)事件的發(fā)生都有一定的概率，比如明天天氣可以由“晴、多云、陰、雨”幾個(gè)事件組合而成，最終哪種天氣會(huì)出現(xiàn)，今天是不確定的，今天只是知道明天各種天氣的發(fā)生概率，并且知道所有各種天氣出現(xiàn)的概率總和為1。我們來(lái)看看事件集合中發(fā)生某事
86、件的信息大小和該事件發(fā)生的概率之間的關(guān)系。某事件發(fā)生的概率越小，該事件發(fā)生后給我們的“震撼”越大。比如“明天發(fā)生、不發(fā)生地震”這一事件集合中，明天不發(fā)生地震的概率遠(yuǎn)大于發(fā)生地震的概率，所以真的明天發(fā)生了地震，那我們所獲得的信息量就比沒(méi)有發(fā)生地震要大的多。此外，信息具有可加性，“今天地震了又下雨”給我們的信息應(yīng)該是今天發(fā)生了地震和今天下雨兩個(gè)事件的信息的和，而兩個(gè)事件同時(shí)發(fā)生的概率又是這兩個(gè)事件各自發(fā)生概率的乘積，基于此，香農(nóng)將某一“發(fā)生概率為P”的事件的出現(xiàn)帶來(lái)的信息量定義為1/P的對(duì)數(shù)，即log1/P。
87、基數(shù)r的不同，使得信息r量可以有不同的單位，基數(shù)r=2，單位就是比特。比如拋一枚硬幣結(jié)果是“國(guó)徽向上”的信息量是log1(12)=1比特。2好，我們僅用這一點(diǎn)信息理論，就可以解決上面提出來(lái)的那個(gè)稱(chēng)球問(wèn)題了。我們的想法是，如果確定12個(gè)球當(dāng)中的壞球需要的信息量是A，而從每次天平的稱(chēng)量結(jié)果可以至少獲得的信息量是B，那不小于A/B的整數(shù)就應(yīng)該是所需的最小的稱(chēng)量次數(shù)了。在稱(chēng)以前，十二只球的任何一個(gè)都可能是壞球，而且概率一樣，都是1/1
