資源描述：
《算法合集之《一類稱球問題的解法》.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、一類稱球問題的解法問題的提出給定N個球有個比標準球重的次品混入其中你有一架天平，用最少的次數(shù)找出這個次品。N=312312①是次品12②是次品12③是次品N=3時稱1次就可以找出次品N=9123456789ABCAB次品在A中次品在B中AB通過一次稱量，可以把次品可能存在的范圍從9個，縮小到3個N=3的時候一次就能稱出次品N=9時稱2次次品在C中AB更一般的情況N=3k12k……12k……12k……ABC更一般的情況ABABAB次品在A中次品在B中次品在C中范圍縮小到原來的1/3更一般的情況n=3k+
2、1,n=3k+2和n=3k類似，也是均分成三堆每次稱量把范圍大致縮小到原來的1/3因此：從n個球中找次品至多要稱[log3n]次。（[]統(tǒng)一表示取上整）判定樹[log3n]無疑是可行解。最優(yōu)性為什么三分？因為天平只有三種可能：左偏、右偏、平衡判定樹稱(1,2)>=<132葉子代表結(jié)果非葉子代表一次稱量每個非葉子節(jié)點都有三個孩子，表示天平左偏、右偏、平衡判定樹比較(1,2,3)與(4,5,6)>=<比較(1)與(2)>13=<2比較(7)與(8)>79=<8比較(4)與(5)>46=<5判定樹的深度就是
3、稱量次數(shù)一個有意義的判定樹至少n個葉子節(jié)點判定樹N個葉子的三叉樹的深度h>=[log3n][log3n]是最優(yōu)解小結(jié)引進了有力工具：判定樹。將主觀的直覺嚴謹化。三分法是解決這類問題的根本著眼點。三分時必須充分的均勻分配的均勻性123……9稱(1,2)><1次品2次品=3…9都可能是次品N個葉子的三叉樹的深度h>=[log3n]深度很大，遠超過其兄弟問題2的提出N個球，混入了一個輕重不詳?shù)拇纹肥种杏幸患芴炱胶鸵粋€標準球用最少的次數(shù)稱出次品并求出次品的輕重問題2的基本分析12可得如下信息：次品若在①中，則
4、它偏重。次品若在②中，則它偏輕。引理的提出已知兩堆球，第一堆有a個、第二堆有b個。若次品在第一堆，必是重球若次品在第二堆，必是輕球分析總共a+b個球每個球都有可能是次品判定樹至少a+b個葉子樹的深度h>=[log3(a+b)]只要稱[log3(a+b)]次就能找到次品引理的分析a=3p……p個……p個……p個A1A2A3b=3q……p個B1B2B3……p個……p個引理的分析A1B1A2B2A3B3次品在A1或者B2范圍被縮小到p+q個球里面引理的分析A1B1A2B2A3B3次品在B1或者A2范圍被縮小
5、到p+q個球里面引理的分析A3B3次品在A3或者B3范圍被縮小到p+q個球里面A1B1A2B2子問題的分析總共a+b=3(p+q)個球無論天平怎么偏，都可以把范圍縮小到p+q個球中，即原來的1/3根據(jù)a,bmod3的余數(shù)分類，上面討論的是amod3=bmod3=0的情況。其他情況可類似進行。關(guān)鍵要“均”分。引理中問題稱[log3(a+b)]次即可。問題2的分析n個球，每個球都有可能是輕球或者重球，有2n種不同的可能結(jié)果判定樹至少要2n個葉子節(jié)點判定樹的深度h>=[log3(2n)]問題2的分析比較S與
6、1>=<1L比較S與2>2L/=<2H1HN=2接著對n歸納問題2的分析n=3p……p個……p個……p個A1A2A3假設(shè)小于n的球都能在[log3(2n)]次內(nèi)稱出次品問題2的分析A1A2A1中的球只可能重A2中的球只可能輕。A1A2A2中的球只可能重A1中的球只可能輕。天平不平衡，次品必在A1或者A2中歸結(jié)到引理，只要稱[log3(p+p)]次問題2的分析A1A2次品在A3中，根據(jù)歸納假設(shè)，還要稱[log3(2p)]次無論天平怎么偏，稱完一次后都還要稱[log3(2p)]次共稱[log3(2p)]+
7、1=[log3(6p)]=[log3(2n)]次問題2的分析稱(A1,A2)><=A1重或A2輕2p個葉子節(jié)點A1輕或A2重2p個葉子節(jié)點A3輕重都有可能2p個葉子節(jié)點
8、A1
9、=
10、A2
11、=
12、A3
13、=p總共有6p個葉子節(jié)點問題2的分析n=3k+2分法
14、A1
15、=k+1
16、A2
17、=k+1
18、A3
19、=k6k+4個葉子節(jié)點分攤到每個孩子是：2k+22k+22k是均勻的問題2的分析N=3k+1分法一：k，k，k+1分攤的葉子節(jié)點：2k，2k，2k+2分法二：k+標準球，k+1，k分攤的葉子節(jié)點：2k+1，2k+1，2
20、k問題2的小結(jié)[log3(2n)]即是問題2的解。最優(yōu)性和可行性均已證明判定樹是一種估界和證明最優(yōu)性的有力工具。通過對判定樹的研究，衍生了一條重要的原則：均勻。均分的對象不是球，而是葉子節(jié)點（即不同的結(jié)果）。其他形式只要求次品，不求輕重。結(jié)論是[log3(2n-1)]問題2去掉標準球。第一次稱的時候就不能保證一定均勻。結(jié)論是[log3(2n+2)]萬變不離其宗，解決此問題的精髓在四個字：均勻三分總結(jié)1、從簡單入手2、求同存異3、嚴謹細心
