資源描述：
《一類稱球問題的解法.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、一類稱球問題的解法長沙雅禮中學(xué)何林關(guān)鍵字判定樹三分均勻摘要本文對一類天平稱球問題提出了完整、嚴(yán)謹(jǐn)?shù)慕夥?，在此基礎(chǔ)上總結(jié)了研究過程中的一些心得和方法。引言有n（n≥3）個球，其中一個是次品，你有一架天平?，F(xiàn)在要稱出哪個次品來。問題1已知次品的重量比其他的要重一些。問題2不知道次品的重量。問題3不知道次品的重量。不僅要求出次品，還要求次品的輕重。問題4不知道次品的重量，要求次品和次品的輕重。另外你手里還得到了一個標(biāo)準(zhǔn)球。面對這一系列類似的問題，我們該從何入手？簡單問題的分析先來考慮最簡單的問題1。為了
2、方便敘述，把n個球按1,2,…,n順次編號。若n=3，把一號球放在天平左邊、二號球放在天平右邊。如果天平：1、左偏，一號重，是次品。2、右偏，二號重，是次品。3、保持平衡，那么一、二都是正常的球，因此就只有可能三號球是次品了。因此n=3，至多一次就能稱出哪個是次品。記作f(3)=1。下面考慮n=9。把所有的球分成三組：A{1,2,3},B{4,5,6},C{7,8,9}。A組的球放在左邊、B組放在右邊。如果天平：1、左偏，則次品在A組里面。1、右偏，則次品在B組里面。2、保持平衡，次品在C組里面。
3、無論在哪個組里面，我們已經(jīng)把次品的范圍從“9”縮小到了“3”，也就是減少到原來的1/3。之前我們已經(jīng)研究過，3個球1次就能稱出來，故而f(9)=2。不難推廣到一般的情況：定理1.1f(3n)=n。證明：n=1,2時，已證。設(shè)n=k成立，則f(3k)=k；下面考慮n=k+1的情況。將3k+1個球分成三堆A,B,C，使得
4、A
5、=
6、B
7、=
8、C
9、=3k。把A放在天平左邊、B放在右邊，天平：1、左偏，次品在A2、右偏，次品在B3、平衡，次品在C無論哪種結(jié)果，我們都把次品的范圍縮小到了3k個球里面。而f(3k
10、)=k，故而f(3k+1)=k+1。綜上，定理1.1成立。稍經(jīng)分析不難得到：定理1.2f(n)=這個的證明和定理1.1完全類似，分nmod3=0,1,2適當(dāng)討論即可。我們必須注意到是可行的，因為我們能夠構(gòu)造出這樣一個方案。問題是它是否最優(yōu)？我們采取的方案是每次將球盡量均勻的三分，這樣做的根據(jù)就是天平只有三種結(jié)果：左偏、右偏、平衡。于是就能保證無論次品在哪一份都能將結(jié)果的范圍縮小到原來的1/3。從感性上認(rèn)識，應(yīng)該就是最優(yōu)解了。為了更加嚴(yán)格的證明的最優(yōu)性，我們引進(jìn)判定樹的概念。下圖就是n=9時的一種判
11、定樹：比較(1,2,3)與(4,5,6)>=<比較(1)與(2)>13=<2比較(7)與(8)>79=<8比較(4)與(5)>46=<5此題的判定樹是這樣一棵樹：1、葉子節(jié)點(diǎn)代表一種可能的結(jié)果。2、非葉子節(jié)點(diǎn)代表一次稱量。3、非葉子節(jié)點(diǎn)至多有三個兒子，分別代表天平的左偏、右偏、平衡三種情況。任意一種稱量方案都能唯一的表示成一棵判定樹；反過來一棵判定樹也唯一對應(yīng)一種稱量方案。容易看出判定樹的深度就是稱量次數(shù)。這就是我們之所以引進(jìn)它的原因。做出判斷之前，誰也無法預(yù)知哪個球是次品，每個都有可能是我們的目
12、標(biāo)；因此一個有意義的判定樹應(yīng)該具有至少n個葉子節(jié)點(diǎn)。n個葉子節(jié)點(diǎn)的樹的深度h≥，故而可以證明，f(n)=是最優(yōu)的。至此完整的解決了問題1。我們的結(jié)論是：有n（n≥3）個球，其中一個是次品，次品的重量比其他的要重一些。給一架天平，至少稱次，就能找出那個次品。具體的方案是將球每次都盡量均勻的三分。（詳見上文）讓我們總結(jié)一下。“三分”是整個算法的核心。我們選擇三分，而不是二分或者四分是有原因的，它的本質(zhì)是由判定樹的特殊結(jié)構(gòu)——三叉樹——所決定的。同時還必須注意一點(diǎn)，我們在三分的時候有兩個字很講究：“均勻
13、”。實際上h≥中的“=”當(dāng)且僅當(dāng)球被均勻的分配時才能達(dá)到。這里說的“均勻”是指“在最壞情況下獲得最好的效果”。因為一棵樹的深度是由它根節(jié)點(diǎn)兒子中深度最大的兒子決定的，為了使得整個樹深度最小，我們就要務(wù)必使得深度最大的兒子深度最小，這就是“均勻”分配的理論根據(jù)?；蛟S你覺得這些總結(jié)是顯然的、多余的廢話。面對一個簡單的問題，你當(dāng)然能夠游刃有余，也不需要提煉出什么經(jīng)驗、方法；可是當(dāng)問題被復(fù)雜化、隱蔽化，你還能如此得心應(yīng)手嗎？稱球問題的拓展一、問題的提出與初步分析問題4有n（n≥3）個球，其中一個是次品，已
14、知：1、次品的重量與其他的球不同，不知道輕重。2、你有一架天平和一個標(biāo)準(zhǔn)球問至少要稱多少次，才能找出那個次品，并且知道次品是輕還是重？我們很自然的聯(lián)想到問題1，試著應(yīng)用三分。把n個球分成三堆，第一堆放在天平左邊、第二堆放在天平右邊。天平平衡，毫無疑問，次品在第三堆中；但問題是如果天平發(fā)生了偏移，既可能第一堆中混入了一個重球、也可能第二堆中混入了一個輕球。我們根本無法準(zhǔn)確地判斷次品具體在哪堆中。問題4較之問題1最大的困難就在于不知道次品的輕重，因此一次稱量之后根本無法馬上將次品縮小到
