第2講 枚舉及篩選2

《第2講 枚舉及篩選2》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第二講枚舉與篩選（二）【競(jìng)技搏擊】例1、下圖中有6個(gè)點(diǎn)，9條線段。一只甲蟲(chóng)從A點(diǎn)出發(fā)要沿著某幾條線段爬到F點(diǎn)，行進(jìn)中同一個(gè)點(diǎn)或同一條線段上只能經(jīng)過(guò)一次，這只甲蟲(chóng)最多有多少種不同的走法？分析與解：為了不重不漏地把所有走法都數(shù)出來(lái)，可以利用畫(huà)枝形圖的方法來(lái)枚舉。所謂枝形圖就是畫(huà)一個(gè)樹(shù)枝形狀的圖，用它來(lái)表示每一步可能的走法，可以非常直觀形象地得到問(wèn)題的答案。甲蟲(chóng)從A點(diǎn)出發(fā)，第一步可有三種不同的走法，即先到B點(diǎn)，先到E點(diǎn)，先到D點(diǎn)。由B點(diǎn)到F點(diǎn)，又有3種不同的走法；直接到F點(diǎn)；經(jīng)C點(diǎn)到F點(diǎn)；經(jīng)E點(diǎn)到F點(diǎn)。由D.E兩點(diǎn)到F點(diǎn)，也有3種不同的走法，請(qǐng)

2、你想一想可以怎樣走，在括號(hào)內(nèi)填上合適的字母。通過(guò)畫(huà)枝形圖枚舉，可直觀看出一共有9種不同走法。利用這種方法考慮一些稍復(fù)雜的問(wèn)題時(shí)，經(jīng)常需要畫(huà)出幾組枝形圖。例2、乒乓球團(tuán)體比賽，采取五盤(pán)三勝制，即兩個(gè)隊(duì)進(jìn)行比賽，哪個(gè)隊(duì)先勝了三盤(pán)就取得了比賽的勝利，現(xiàn)在A、B兩隊(duì)進(jìn)行比賽，A隊(duì)最終獲勝，請(qǐng)問(wèn)：各盤(pán)的勝負(fù)情況有多少種可能？８分析與解：兩個(gè)隊(duì)的總比分有3種情況，即：A隊(duì)以3：0勝，A隊(duì)以3：1勝，A隊(duì)以3：2獲勝。這樣，我們就可以分三類，畫(huà)枝形圖枚舉出各盤(pán)的勝負(fù)情況。若A隊(duì)以3：0勝，只能有一種情況，可以表示為（A-A-A）說(shuō)明共比賽3盤(pán)，都A獲勝

3、。若A隊(duì)以3：1勝，說(shuō)明共比賽4盤(pán)，所以有3種可能，可以這樣畫(huà)枝形圖（如圖1）。圖1圖2若A隊(duì)以3：2勝，說(shuō)明共比賽5盤(pán)，B隊(duì)勝了2盤(pán)?？赡蹵隊(duì)先勝第一盤(pán)，也可能有B隊(duì)先勝第一盤(pán)。請(qǐng)你按這兩類考慮后面4盤(pán)的勝負(fù)情況，在括號(hào)內(nèi)填勝隊(duì)字母，完成枝形圖（如圖2）。所以各盤(pán)的勝負(fù)情況有1＋3＋6=10（種）可能。這道題，我們先從整體上進(jìn)行分類，然后畫(huà)枝形圖枚舉出每一類中的可能情況，這種枚舉方法可以幫助我們解答一些比較復(fù)雜的計(jì)數(shù)問(wèn)題。例3、用一元錢(qián)購(gòu)買(mǎi)2分郵票或4分郵票或8分郵票若干張，沒(méi)有剩余錢(qián)，一共可以有多少種不同的買(mǎi)法？分析與解：根據(jù)題意，用

4、1元錢(qián)也就是100分錢(qián)，可以買(mǎi)三種郵票，也可以買(mǎi)其中的兩種，還可以只買(mǎi)一種，只要沒(méi)有剩余錢(qián)就可以。所以不同的買(mǎi)法會(huì)很多，一一枚舉出來(lái)會(huì)很困難。我們可以用列表的方法來(lái)枚舉，因?yàn)?分郵票最多可以買(mǎi)12張，最少可以買(mǎi)0張，因此分類可以畫(huà)出下表。８8分郵票張數(shù)1211109876543210合計(jì)買(mǎi)法種數(shù)4分郵票張數(shù)1030507090110130150170190210230250買(mǎi)法種數(shù)2468101214161820222426182表中沒(méi)有考慮買(mǎi)2分郵票的張數(shù)，因?yàn)橘I(mǎi)8分郵票的張數(shù)確定后，4分郵票有幾種買(mǎi)法，2分郵票就有幾種買(mǎi)法。我們先來(lái)考

5、慮第一類的買(mǎi)法種數(shù)，8分郵票買(mǎi)12張，還剩4分錢(qián)，4分郵票可以買(mǎi)1張，也可以買(mǎi)0張，有兩種買(mǎi)法。再考慮第二類，8分郵票買(mǎi)11張，還剩12分錢(qián)，4分郵票最多可以買(mǎi)3張，最少可以買(mǎi)0張，共有4種買(mǎi)法，我們?cè)?和0之間點(diǎn)上省略號(hào)，簡(jiǎn)單表示4分郵票買(mǎi)的張數(shù)。請(qǐng)你用這種方法考慮下面各類的買(mǎi)法種數(shù)，并算出合計(jì)買(mǎi)法種數(shù)填在表中。所以一共有182種不同的買(mǎi)法。通過(guò)解答這道題，我們知道了，如果考慮的情況比較多，就可以利用列表的方法來(lái)枚舉。為了提高這種枚舉方法的解題速度，我們要善于在列表過(guò)程中發(fā)現(xiàn)規(guī)律，利用這個(gè)規(guī)律，幫助我們解答問(wèn)題。例4、對(duì)自然數(shù)列1、2、

6、3、4、5……進(jìn)行淘汰。淘汰原則是：凡不能表示為兩個(gè)合數(shù)之和的自然數(shù)均被淘汰。如：“1”應(yīng)被淘汰，但12可以寫(xiě)成兩個(gè)合數(shù)8與4的和，不應(yīng)被淘汰。那么保留下來(lái)的數(shù)從小到大數(shù)下去，第2000個(gè)數(shù)是多少？分析與解：根據(jù)題意，要想直接考慮第2000個(gè)數(shù)是多少，比較困難，我們可以從反面枚舉出所有被淘汰的數(shù)，知道淘汰了幾個(gè)數(shù)，就能求出剩下的第2000個(gè)數(shù)是多少了。請(qǐng)你根據(jù)按從小到大的順序找出三個(gè)偶合數(shù)，再找出最小的奇合數(shù)，填在下面括號(hào)內(nèi)。偶合數(shù)：（4）、（6）、（8）…；最小的奇合數(shù)是（9）因?yàn)?+4=8，4+6=10，4+8=12說(shuō)明從8開(kāi)始的偶數(shù)

7、都能寫(xiě)成兩個(gè)合數(shù)的和不能被淘汰。而4+9=13，6+9=15，8+9=17，說(shuō)明從13開(kāi)始的奇數(shù)也都不應(yīng)被淘汰。所以被淘汰的數(shù)有（1、2、3、4、5、6、7、9、11）共有9個(gè)。所以保留下的第2000個(gè)數(shù)是2000＋9=2009。注：本題是從事物的反面枚舉的。８例5、有一批長(zhǎng)度分別為1、2、3、4………11厘米的細(xì)木條，它們的數(shù)量都是足夠多，從中適當(dāng)選取三根木條作為三條邊，可圍成一個(gè)三角形，如果規(guī)定底邊長(zhǎng)是11厘米，你能圍成多少種不同的三角形？分析與解：題中規(guī)定了三角形底邊長(zhǎng)是11厘米，所以要求能圍成多少種不同的三角形，只需考慮另外兩條邊

8、也有多少種選法。要使選出的兩根木條與規(guī)定的11厘米長(zhǎng)的木條能圍成三角形，這兩根木條長(zhǎng)度和必須大于11厘米。有一根長(zhǎng)11厘米，另外一根可以選擇1、2、3、4……11厘米的木條，有11種不同選法。