國(guó)家集訓(xùn)隊(duì)2003論文集 何林

《國(guó)家集訓(xùn)隊(duì)2003論文集 何林》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、一類(lèi)稱(chēng)球問(wèn)題的解法問(wèn)題的提出給定N個(gè)球有個(gè)比標(biāo)準(zhǔn)球重的次品混入其中你有一架天平，用最少的次數(shù)找出這個(gè)次品。N=312312①是次品12②是次品12③是次品N=3時(shí)稱(chēng)1次就可以找出次品N=9123456789ABCAB次品在A中次品在B中AB通過(guò)一次稱(chēng)量，可以把次品可能存在的范圍從9個(gè)，縮小到3個(gè)N=3的時(shí)候一次就能稱(chēng)出次品N=9時(shí)稱(chēng)2次次品在C中AB更一般的情況N=3k12k……12k……12k……ABC更一般的情況ABABAB次品在A中次品在B中次品在C中范圍縮小到原來(lái)的1/3更一般的情況n=3k+1,n=3k+2和n=3k類(lèi)似，也是均分成三堆每次稱(chēng)量把范圍大

2、致縮小到原來(lái)的1/3因此：從n個(gè)球中找次品至多要稱(chēng)[log3n]次。（[]統(tǒng)一表示取上整）判定樹(shù)[log3n]無(wú)疑是可行解。最優(yōu)性為什么三分？因?yàn)樘炱街挥腥N可能：左偏、右偏、平衡判定樹(shù)稱(chēng)(1,2)>=<132葉子代表結(jié)果非葉子代表一次稱(chēng)量每個(gè)非葉子節(jié)點(diǎn)都有三個(gè)孩子，表示天平左偏、右偏、平衡判定樹(shù)比較(1,2,3)與(4,5,6)>=<比較(1)與(2)>13=<2比較(7)與(8)>79=<8比較(4)與(5)>46=<5判定樹(shù)的深度就是稱(chēng)量次數(shù)一個(gè)有意義的判定樹(shù)至少n個(gè)葉子節(jié)點(diǎn)判定樹(shù)N個(gè)葉子的三叉樹(shù)的深度h>=[log3n][log3n]是最優(yōu)解小結(jié)引進(jìn)了有

3、力工具：判定樹(shù)。將主觀的直覺(jué)嚴(yán)謹(jǐn)化。三分法是解決這類(lèi)問(wèn)題的根本著眼點(diǎn)。三分時(shí)必須充分的均勻分配的均勻性123……9稱(chēng)(1,2)><1次品2次品=3…9都可能是次品N個(gè)葉子的三叉樹(shù)的深度h>=[log3n]深度很大，遠(yuǎn)超過(guò)其兄弟問(wèn)題2的提出N個(gè)球，混入了一個(gè)輕重不詳?shù)拇纹肥种杏幸患芴炱胶鸵粋€(gè)標(biāo)準(zhǔn)球用最少的次數(shù)稱(chēng)出次品并求出次品的輕重問(wèn)題2的基本分析12可得如下信息：次品若在①中，則它偏重。次品若在②中，則它偏輕。引理的提出已知兩堆球，第一堆有a個(gè)、第二堆有b個(gè)。若次品在第一堆，必是重球若次品在第二堆，必是輕球分析總共a+b個(gè)球每個(gè)球都有可能是次品判定樹(shù)至少a+b個(gè)

4、葉子樹(shù)的深度h>=[log3(a+b)]只要稱(chēng)[log3(a+b)]次就能找到次品引理的分析a=3p……p個(gè)……p個(gè)……p個(gè)A1A2A3b=3q……p個(gè)B1B2B3……p個(gè)……p個(gè)引理的分析A1B1A2B2A3B3次品在A1或者B2范圍被縮小到p+q個(gè)球里面引理的分析A1B1A2B2A3B3次品在B1或者A2范圍被縮小到p+q個(gè)球里面引理的分析A3B3次品在A3或者B3范圍被縮小到p+q個(gè)球里面A1B1A2B2子問(wèn)題的分析總共a+b=3(p+q)個(gè)球無(wú)論天平怎么偏，都可以把范圍縮小到p+q個(gè)球中，即原來(lái)的1/3根據(jù)a,bmod3的余數(shù)分類(lèi)，上面討論的是amod3

5、=bmod3=0的情況。其他情況可類(lèi)似進(jìn)行。關(guān)鍵要“均”分。引理中問(wèn)題稱(chēng)[log3(a+b)]次即可。問(wèn)題2的分析n個(gè)球，每個(gè)球都有可能是輕球或者重球，有2n種不同的可能結(jié)果判定樹(shù)至少要2n個(gè)葉子節(jié)點(diǎn)判定樹(shù)的深度h>=[log3(2n)]問(wèn)題2的分析比較S與1>=<1L比較S與2>2L/=<2H1HN=2接著對(duì)n歸納問(wèn)題2的分析n=3p……p個(gè)……p個(gè)……p個(gè)A1A2A3假設(shè)小于n的球都能在[log3(2n)]次內(nèi)稱(chēng)出次品問(wèn)題2的分析A1A2A1中的球只可能重A2中的球只可能輕。A1A2A2中的球只可能重A1中的球只可能輕。天平不平衡，次品必在A1或者A2中歸結(jié)

6、到引理，只要稱(chēng)[log3(p+p)]次問(wèn)題2的分析A1A2次品在A3中，根據(jù)歸納假設(shè)，還要稱(chēng)[log3(2p)]次無(wú)論天平怎么偏，稱(chēng)完一次后都還要稱(chēng)[log3(2p)]次共稱(chēng)[log3(2p)]+1=[log3(6p)]=[log3(2n)]次問(wèn)題2的分析稱(chēng)(A1,A2)><=A1重或A2輕2p個(gè)葉子節(jié)點(diǎn)A1輕或A2重2p個(gè)葉子節(jié)點(diǎn)A3輕重都有可能2p個(gè)葉子節(jié)點(diǎn)

7、A1

8、=

9、A2

10、=

11、A3

12、=p總共有6p個(gè)葉子節(jié)點(diǎn)問(wèn)題2的分析n=3k+2分法

13、A1

14、=k+1

15、A2

16、=k+1

17、A3

18、=k6k+4個(gè)葉子節(jié)點(diǎn)分?jǐn)偟矫總€(gè)孩子是：2k+22k+22k是均勻的問(wèn)題2的分析N=

19、3k+1分法一：k，k，k+1分?jǐn)偟娜~子節(jié)點(diǎn)：2k，2k，2k+2分法二：k+標(biāo)準(zhǔn)球，k+1，k分?jǐn)偟娜~子節(jié)點(diǎn)：2k+1，2k+1，2k問(wèn)題2的小結(jié)[log3(2n)]即是問(wèn)題2的解。最優(yōu)性和可行性均已證明判定樹(shù)是一種估界和證明最優(yōu)性的有力工具。通過(guò)對(duì)判定樹(shù)的研究，衍生了一條重要的原則：均勻。均分的對(duì)象不是球，而是葉子節(jié)點(diǎn)（即不同的結(jié)果）。其他形式只要求次品，不求輕重。結(jié)論是[log3(2n-1)]問(wèn)題2去掉標(biāo)準(zhǔn)球。第一次稱(chēng)的時(shí)候就不能保證一定均勻。結(jié)論是[log3(2n+2)]萬(wàn)變不離其宗，解決此問(wèn)題的精髓在四個(gè)字：均勻三分總結(jié)1、從簡(jiǎn)單入手2、求同存異3、嚴(yán)

20、謹(jǐn)細(xì)心