算法合集之《一類稱球問題的解法》

《算法合集之《一類稱球問題的解法》》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、一類稱球問題的解法長(zhǎng)沙雅禮中學(xué)何林關(guān)鍵字判定樹三分均勻摘要本文對(duì)一類天平稱球問題提出了完整、嚴(yán)謹(jǐn)?shù)慕夥ǎ诖嘶A(chǔ)上總結(jié)了研究過程中的一些心得和方法。引言有n（n≥3）個(gè)球，其中一個(gè)是次品，你有一架天平?，F(xiàn)在要稱出哪個(gè)次品來。問題1已知次品的重量比其他的要重一些。問題2不知道次品的重量。問題3不知道次品的重量。不僅要求出次品，還要求次品的輕重。問題4不知道次品的重量，要求次品和次品的輕重。另外你手里還得到了一個(gè)標(biāo)準(zhǔn)球。面對(duì)這一系列類似的問題，我們?cè)搹暮稳胧?？?jiǎn)單問題的分析先來考慮最簡(jiǎn)單的問題1。為了方便敘述，把n個(gè)球按1,2

2、,…,n順次編號(hào)。若n=3，把一號(hào)球放在天平左邊、二號(hào)球放在天平右邊。如果天平：1、左偏，一號(hào)重，是次品。2、右偏，二號(hào)重，是次品。3、保持平衡，那么一、二都是正常的球，因此就只有可能三號(hào)球是次品了。因此n=3，至多一次就能稱出哪個(gè)是次品。記作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組里面。無論在哪個(gè)組里面，我們已經(jīng)把次品的范圍從“9”縮小到

3、了“3”，也就是減少到原來的1/3。之前我們已經(jīng)研究過，3個(gè)球1次就能稱出來，故而f(9)=2。不難推廣到一般的情況：定理1.1f(3n)=n。證明：n=1,2時(shí)，已證。設(shè)n=k成立，則f(3k)=k；下面考慮n=k+1的情況。將3k+1個(gè)球分成三堆A,B,C，使得

4、A

5、=

6、B

7、=

8、C

9、=3k。把A放在天平左邊、B放在右邊，天平：1、左偏，次品在A2、右偏，次品在B3、平衡，次品在C無論哪種結(jié)果，我們都把次品的范圍縮小到了3k個(gè)球里面。而f(3k)=k，故而f(3k+1)=k+1。綜上，定理1.1成立。稍經(jīng)分析不難得到：定

10、理1.2f(n)=這個(gè)的證明和定理1.1完全類似，分nmod3=0,1,2適當(dāng)討論即可。我們必須注意到是可行的，因?yàn)槲覀兡軌驑?gòu)造出這樣一個(gè)方案。問題是它是否最優(yōu)？我們采取的方案是每次將球盡量均勻的三分，這樣做的根據(jù)就是天平只有三種結(jié)果：左偏、右偏、平衡。于是就能保證無論次品在哪一份都能將結(jié)果的范圍縮小到原來的1/3。從感性上認(rèn)識(shí)，應(yīng)該就是最優(yōu)解了。為了更加嚴(yán)格的證明的最優(yōu)性，我們引進(jìn)判定樹的概念。下圖就是n=9時(shí)的一種判定樹：比較(1,2,3)與(4,5,6)>=<比較(1)與(2)>13=<2比較(7)與(8)>79=<

11、8比較(4)與(5)>46=<5此題的判定樹是這樣一棵樹：1、葉子節(jié)點(diǎn)代表一種可能的結(jié)果。2、非葉子節(jié)點(diǎn)代表一次稱量。3、非葉子節(jié)點(diǎn)至多有三個(gè)兒子，分別代表天平的左偏、右偏、平衡三種情況。任意一種稱量方案都能唯一的表示成一棵判定樹；反過來一棵判定樹也唯一對(duì)應(yīng)一種稱量方案。容易看出判定樹的深度就是稱量次數(shù)。這就是我們之所以引進(jìn)它的原因。做出判斷之前，誰也無法預(yù)知哪個(gè)球是次品，每個(gè)都有可能是我們的目標(biāo)；因此一個(gè)有意義的判定樹應(yīng)該具有至少n個(gè)葉子節(jié)點(diǎn)。n個(gè)葉子節(jié)點(diǎn)的樹的深度h≥，故而可以證明，f(n)=是最優(yōu)的。至此完整的解決了

12、問題1。我們的結(jié)論是：有n（n≥3）個(gè)球，其中一個(gè)是次品，次品的重量比其他的要重一些。給一架天平，至少稱次，就能找出那個(gè)次品。具體的方案是將球每次都盡量均勻的三分。（詳見上文）讓我們總結(jié)一下。“三分”是整個(gè)算法的核心。我們選擇三分，而不是二分或者四分是有原因的，它的本質(zhì)是由判定樹的特殊結(jié)構(gòu)——三叉樹——所決定的。同時(shí)還必須注意一點(diǎn)，我們?cè)谌值臅r(shí)候有兩個(gè)字很講究：“均勻”。實(shí)際上h≥中的“=”當(dāng)且僅當(dāng)球被均勻的分配時(shí)才能達(dá)到。這里說的“均勻”是指“在最壞情況下獲得最好的效果”。因?yàn)橐豢脴涞纳疃仁怯伤?jié)點(diǎn)兒子中深度最大的兒

13、子決定的，為了使得整個(gè)樹深度最小，我們就要?jiǎng)?wù)必使得深度最大的兒子深度最小，這就是“均勻”分配的理論根據(jù)?；蛟S你覺得這些總結(jié)是顯然的、多余的廢話。面對(duì)一個(gè)簡(jiǎn)單的問題，你當(dāng)然能夠游刃有余，也不需要提煉出什么經(jīng)驗(yàn)、方法；可是當(dāng)問題被復(fù)雜化、隱蔽化，你還能如此得心應(yīng)手嗎？稱球問題的拓展一、問題的提出與初步分析問題4有n（n≥3）個(gè)球，其中一個(gè)是次品，已知：1、次品的重量與其他的球不同，不知道輕重。2、你有一架天平和一個(gè)標(biāo)準(zhǔn)球問至少要稱多少次，才能找出那個(gè)次品，并且知道次品是輕還是重？我們很自然的聯(lián)想到問題1，試著應(yīng)用三分。把n個(gè)球

14、分成三堆，第一堆放在天平左邊、第二堆放在天平右邊。天平平衡，毫無疑問，次品在第三堆中；但問題是如果天平發(fā)生了偏移，既可能第一堆中混入了一個(gè)重球、也可能第二堆中混入了一個(gè)輕球。我們根本無法準(zhǔn)確地判斷次品具體在哪堆中。問題4較之問題1最大的困難就在于不知道次品的輕重，因此一次稱量之后根本無法馬上將次品縮小到