《《找次品問題》方法》由會(huì)員分享,可在線閱讀,更多相關(guān)《《找次品問題》方法(2頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、
《找次品問題》的求解方法
? ? ? ? ? ? ? ? ? ? ? ?
? ?還是從比爾·蓋茨與81個(gè)玻璃球的問題說開來吧。
???(1)?小比爾·蓋茨的問題:這兒有81個(gè)玻璃球,其中有一個(gè)球比其他的球稍重,如果只能用天平來測(cè)量,至少要稱多少次才能保證找出來呢?
???(2)?如果不知道次品玻璃球與標(biāo)準(zhǔn)球的輕重,同樣只用天平來測(cè)量,至少要稱多少次才能保證找出次品玻璃球來?
怎樣用天平來測(cè)量次品?就是要用天平稱量時(shí)的“平衡”與“不平衡”來判斷研究對(duì)象的情況。“平衡”判明沒次品;“不平衡”判明次品就在這里。本題要求最少的稱量次數(shù),顯然還要找出一個(gè)解決問題的最優(yōu)策略,也就是要讓天平每
2、稱量一次能判斷的研究對(duì)象個(gè)數(shù)最多,最終達(dá)到稱量次數(shù)最少的目的。實(shí)際操作起來就是把研究對(duì)象怎樣分組,分成多少組的問題。
怎樣分組?有平均分(對(duì)于不能平均分的數(shù)量,讓數(shù)量多的組多1個(gè),少的組少1個(gè)),任意分兩種分法。比較起來只有平均分才能讓“平衡”與“不平衡”說明研究對(duì)象的情況(任意分時(shí),天平兩邊數(shù)量不等,“平衡”已不可能,“不平衡”也不能判斷出問題),所以選擇平均分法。
????分成多少組?有分成2組、3組、4組、5組等多種分法。因?yàn)樘炱接袃蓚€(gè)托盤,每稱量一次能放上兩組研究對(duì)象,最多能判斷出3組的情況(既能判斷出天平上兩組的情況,還能判斷出天平外一組的情況。若平衡,次品就在盤外那組中;若不平
3、衡,盤外那組中就無次品),所以只有分成2組或3組才能使天平每稱量一次包括研究對(duì)象的全部,其他組數(shù)達(dá)不到這個(gè)要求——舍棄。再比較2組分法、3組分法的優(yōu)劣:把2組分法、3組分法上次稱量判斷出的問題組對(duì)象再分別2等分之、3等分之??梢缘贸鱿麓畏Q量時(shí)天平每邊的對(duì)象數(shù)量,3組分法的遠(yuǎn)比2組分法的少。繼續(xù)稱量下去,顯然,3組分法的稱量次數(shù)要少,更符合最優(yōu)策略。
綜合起來,就是選擇平均分成3組的分法。
用天平稱量的方法找次品有什么規(guī)律?
因?yàn)椴捎玫氖侨确址?,則每次稱量都是把上次找出的問題組對(duì)象三等分之進(jìn)行研究,且最后一次找出次品時(shí),天平兩邊各只有1個(gè)研究對(duì)象,所以從天平兩邊各放1個(gè)研究對(duì)象開始逆推找
4、規(guī)律。
??????天平稱量法找次品統(tǒng)計(jì)表
次數(shù)
最多判斷出研究對(duì)象的個(gè)數(shù)
1
3=31?????????????????(1,1,1)
2
3×3=9=32????????(3,3,3)(1,1,1)
3
9×3=27=33??????(9,9,9)(3,3,3)(1,1,1)
4
27×3=81=34????(27,27,27)(9,9,9)
???????????????(3,3,?3)(1,1,1)
一般地,用天平稱量n次,能判斷出研究對(duì)象的最多個(gè)數(shù)Y=3n。
上面研究的都是“最多”數(shù)量的情況,不滿足“最多”條件的數(shù)量情況如何呢?比如4、12情況怎樣
5、?
先研究4:因?yàn)樘炱椒Q量1次最多只能判斷出3個(gè),所以要再稱量1?次,一共2次才能有保證。[平衡2次:(2,1,1)→(1,1)。不平衡1次:(2,1,1)。]
再研究12:天平稱量2次最多能判斷出9個(gè),所以也要再稱1次,一共是3次才能有保證。[平衡3次:(4,4,4)→(2,1,1)→(1,1)。不平衡2次:(4,4,4)→(2,1,1)]
一般地,用天平稱量法找次品,當(dāng)研究對(duì)象的個(gè)數(shù)?Y滿足關(guān)系式3n-1<Y≤3n時(shí),最少要稱量n次才能保證找出次品。
現(xiàn)在回頭解答比爾·蓋茨與81個(gè)玻璃球的問題。
????問題(1)小比爾·蓋茨的問題:這兒有81個(gè)玻璃球,其中有一個(gè)球比其他的球稍重
6、,如果只能用天平來測(cè)量,至少要稱多少次才能保證找出來呢?
因?yàn)?1=34,所以最少要稱4次才能保證找出次品。
????問題(2)如果不知道次品玻璃球與標(biāo)準(zhǔn)球的輕重,同樣只用天平來測(cè)量,至少要稱多少次才能保證找出次品玻璃球來?
先測(cè)出次品玻璃球是重了還是輕了:
分組??81÷3=27??????(27,27,27)
1次——任取兩組過天平,有“平衡”與“不平衡”兩種情況。
研究“平衡”情況?????既是“平衡”,就判斷出次品在天平外那組中。
2次——任取已過天平一組與天平外那組同稱,肯定不平衡。若原天平外那組重些,就判斷出次品比標(biāo)準(zhǔn)球重,否則,次品就是比標(biāo)準(zhǔn)球輕。
研究“不平衡”
7、情況?????既是“不平衡”,就判斷出次品已在天平中,天平外那組是標(biāo)準(zhǔn)球。
2次——取較重的一組與天平外那組同稱,有“平衡”、“不平衡”兩種可能。若“平衡”就判斷出次品球比標(biāo)準(zhǔn)球輕;若“不平衡”就判斷出次品球比標(biāo)準(zhǔn)球重。
綜合以上研究得出:最少稱2次才能知道次品球在那組中,也才能知道次品球比標(biāo)準(zhǔn)球是重些還是輕些。此時(shí),次品所在組有球27個(gè)。因?yàn)椋?7=33,所以最少再稱3次才能保證找出次品球來。
一共是???2+3=5(次)
例:若73個(gè)零件,其中有一個(gè)比其他的零件稍重,如果只能用天平來測(cè)量,至少要稱多少次才能保證找出來呢?
解:因?yàn)?3<73≤34,所以最少要稱4次才能保證找出次品。
[平衡4次:(25,24,24)(9,8,8)(3,3,3)(1,1,1)。不平衡4次:(25,24,24)(8,8,8)(3,3,2)(1,1,1)]