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