解排列組合問題的十六種常用策略_第1頁(yè)
解排列組合問題的十六種常用策略_第2頁(yè)
解排列組合問題的十六種常用策略_第3頁(yè)
解排列組合問題的十六種常用策略_第4頁(yè)
解排列組合問題的十六種常用策略_第5頁(yè)
已閱讀5頁(yè),還剩29頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

解排列組合問題的十六種常用策略第1頁(yè),共34頁(yè),2023年,2月20日,星期四三.特殊元素和特殊位置優(yōu)先策略四.相鄰元素捆綁策略五.不相鄰問題插空策略六.定序問題空位插入策略七.重排問題求冪策略八.多排問題直排策略九.排列組合混合問題先選后排策略十.小集團(tuán)問題先整體后局部策略十一.元素相同問題隔板策略二.正難則反總體淘汰策略十二.平均分組問題除法策略一.合理分類與準(zhǔn)確分步策略十三.構(gòu)造模型策略十四.實(shí)際操作窮舉策略十五.分解與合成策略十六.化歸策略解排列組合問題的十六種常用策略第2頁(yè),共34頁(yè),2023年,2月20日,星期四一.合理分類與分步策略例13.在一次演唱會(huì)上共10名演員,其中8人能唱歌,5人會(huì)跳舞,現(xiàn)要演出一個(gè)2人唱歌2人伴舞的節(jié)目,有多少選派方法?解:10演員中有5人只會(huì)唱歌,2人只會(huì)跳舞

3人為全能演員。以只會(huì)唱歌的5人是否選上唱歌為標(biāo)準(zhǔn)進(jìn)行分類.只會(huì)唱歌的5人中沒有人選上唱歌共有____種,只會(huì)唱的5人中只有1人選上唱歌________種,只會(huì)唱的5人中只有2人選上唱歌有____種,由分類計(jì)數(shù)原理共有______________________種。++第3頁(yè),共34頁(yè),2023年,2月20日,星期四本題還有如下分類標(biāo)準(zhǔn):*以3個(gè)全能演員是否選上唱歌人員為標(biāo)準(zhǔn)*以3個(gè)全能演員是否選上跳舞人員為標(biāo)準(zhǔn)*以只會(huì)跳舞的2人是否選上跳舞人員為標(biāo)準(zhǔn)都可經(jīng)得到正確結(jié)果解含有約束條件的排列組合問題,可按元素的性質(zhì)進(jìn)行分類,按事件發(fā)生的連續(xù)過程分步,做到標(biāo)準(zhǔn)明確。分步層次清楚,不重不漏,分類標(biāo)準(zhǔn)一旦確定要貫穿于解題過程的始終。第4頁(yè),共34頁(yè),2023年,2月20日,星期四練習(xí)題例:3成人2小孩乘船游玩,A號(hào)船最多乘3人,B號(hào)船最多乘2人,C號(hào)船只能乘1人,他們?nèi)芜x2只船或3只船,但小孩不能單獨(dú)乘一只船,這3人共有多少乘船方法.首先人數(shù)可以有以下分配A3,B2,C0;A3,B1,C1;A2,B2,C1分情況討論

A3,B2,C0所有可能減去小孩獨(dú)乘的可能(只有一種就是兩個(gè)小孩都在B上)種乘法A2,B2,C1首先A、B、C上肯定都有一個(gè)大人,所以有種乘法A3,B1,C1BC上肯定都是一個(gè)大人,剩下一個(gè)大人和兩個(gè)小孩乘A沒得選:種乘法

共計(jì):9+6+12=27種乘座方法。第5頁(yè),共34頁(yè),2023年,2月20日,星期四二.正難則反總體淘汰策略例11.從0,1,2,3,4,5,6,7,8,9這十個(gè)數(shù)字中取出三個(gè)數(shù),使其和為不小于10的偶數(shù),不同的取法有多少種?解:這問題中如果直接求不小于10的偶數(shù)很困難,可用總體淘汰法。這十個(gè)數(shù)字中有5個(gè)偶數(shù)5個(gè)奇數(shù),所取的三個(gè)數(shù)含有3個(gè)偶數(shù)的取法有____,只含有1個(gè)偶數(shù)的取法有_____,和為偶數(shù)的取法共有_________再淘汰和小于10的偶數(shù)共___________符合條件的取法共有___________9013015017035213215024413026+-9+有些排列組合問題,正面直接考慮比較復(fù)雜,而它的反面往往比較簡(jiǎn)捷,可以先求出它的反面,再?gòu)恼w中淘汰.第6頁(yè),共34頁(yè),2023年,2月20日,星期四1.某班里有43位同學(xué),從中任抽3人,正、副班長(zhǎng)、團(tuán)支部書記至少有一人在內(nèi)的抽法有多少種?練習(xí)題2.從4名男生和3名女生中選出4人參加某個(gè)座談會(huì),若這4人中必須既有男生又有女生,則不同的選法共有_______第7頁(yè),共34頁(yè),2023年,2月20日,星期四三.特殊元素和特殊位置優(yōu)先策略例1.由0,1,2,3,4,5可以組成多少個(gè)沒有重復(fù)數(shù)字五位奇數(shù).

解:由于末位和首位有特殊要求,應(yīng)該優(yōu)先安排,以免不合要求的元素占了這兩個(gè)位置先排末位共有___

然后排首位共有___最后排其它位置共有___由分步計(jì)數(shù)原理得=288第8頁(yè),共34頁(yè),2023年,2月20日,星期四7種不同的花種在排成一列的花盆里,若兩種葵花不種在中間,也不種在兩端的花盆里,問有多少不同的種法?練習(xí)題第9頁(yè),共34頁(yè),2023年,2月20日,星期四四.相鄰元素捆綁策略例2.7人站成一排,其中甲乙相鄰且丙丁相鄰,共有多少種不同的排法.甲乙丙丁由分步計(jì)數(shù)原理可得共有種不同的排法=480解:可先將甲乙兩元素捆綁成整體并看成一個(gè)復(fù)合元素,同時(shí)丙丁也看成一個(gè)復(fù)合元素,再與其它元素進(jìn)行排列,同時(shí)對(duì)相鄰元素內(nèi)部進(jìn)行自排。要求某幾個(gè)元素必須排在一起的問題,可以用捆綁法來解決問題.即將需要相鄰的元素合并為一個(gè)元素,再與其它元素一起作排列,同時(shí)要注意合并元素內(nèi)部也必須排列.第10頁(yè),共34頁(yè),2023年,2月20日,星期四五.不相鄰問題插空策略例3.一個(gè)晚會(huì)的節(jié)目有4個(gè)舞蹈,2個(gè)相聲,3個(gè)獨(dú)唱,舞蹈節(jié)目不能連續(xù)出場(chǎng),則節(jié)目的出場(chǎng)順序有多少種?解:分兩步進(jìn)行第一步排2個(gè)相聲和3個(gè)獨(dú)唱共有

種,第二步將4舞蹈插入第一步排好的5個(gè)元素中間包含首尾兩個(gè)空位共有種

不同的方法

由分步計(jì)數(shù)原理,節(jié)目的不同順序共有

種相相獨(dú)獨(dú)獨(dú)元素相離問題可先把沒有位置要求的元素進(jìn)行排隊(duì)再把不相鄰元素插入中間和兩端第11頁(yè),共34頁(yè),2023年,2月20日,星期四某班新年聯(lián)歡會(huì)原定的5個(gè)節(jié)目已排成節(jié)目單,開演前又增加了兩個(gè)新節(jié)目.如果將這兩個(gè)新節(jié)目插入原節(jié)目單中,且兩個(gè)新節(jié)目不相鄰,那么不同插法的種數(shù)為()

練習(xí)題某人射擊8槍,命中4槍,4槍命中恰好有3槍連在一起的情形的不同種數(shù)為()第12頁(yè),共34頁(yè),2023年,2月20日,星期四六.定序問題空位插入策略例4.7人排隊(duì),其中甲乙丙3人順序一定共有多少不同的排法解:(空位法)設(shè)想有7把椅子讓除甲乙丙以外的四人就坐共有

種方法,其余的三個(gè)位置甲乙丙共有

種坐法,則共有

種方法

1第13頁(yè),共34頁(yè),2023年,2月20日,星期四(插入法)先排甲乙丙三個(gè)人,共有1種排法,再把其余4四人依次插入共有

方法練習(xí)題10人身高各不相等,排成前后排,每排5人,要求從左至右身高逐漸增加,共有多少排法?4*5*6*7第14頁(yè),共34頁(yè),2023年,2月20日,星期四七.重排問題求冪策略例5.把6名實(shí)習(xí)生分配到7個(gè)車間實(shí)習(xí),共有多少種不同的分法解:完成此事共分六步:把第一名實(shí)習(xí)生分配到車間有

種分法.7把第二名實(shí)習(xí)生分配到車間也有7種分法,依此類推,由分步計(jì)數(shù)原理共有種不同的排法允許重復(fù)的排列問題的特點(diǎn)是以元素為研究對(duì)象,元素不受位置的約束,可以逐一安排各個(gè)元素的位置,一般地n不同的元素沒有限制地安排在m個(gè)位置上的排列數(shù)為種nm第15頁(yè),共34頁(yè),2023年,2月20日,星期四某8層大樓一樓電梯上來8名乘客,他們到各自的一層下電梯,下電梯的方法()練習(xí)題第16頁(yè),共34頁(yè),2023年,2月20日,星期四八.多排問題直排策略例7.8人排成前后兩排,每排4人,其中甲乙在前排,丁在后排,共有多少排法解:8人排前后兩排,相當(dāng)于8人坐8把椅子,可以把椅子排成一排.先在前4個(gè)位置排甲乙兩個(gè)特殊元素有____種,再排后4個(gè)位置上的特殊元素有_____種,其余的5人在5個(gè)位置上任意排列有____種,則共有_________種.前排后排一般地,元素分成多排的排列問題,可歸結(jié)為一排考慮,再分段研究.第17頁(yè),共34頁(yè),2023年,2月20日,星期四九.排列組合混合問題先選后排策略例8.有5個(gè)不同的小球,裝入4個(gè)不同的盒內(nèi),

每盒至少裝一個(gè)球,共有多少不同的裝法.解:第一步從5個(gè)球中選出2個(gè)組成復(fù)合元共有__種方法.再把5個(gè)元素(包含一個(gè)復(fù)合元素)裝入4個(gè)不同的盒內(nèi)有_____種方法.根據(jù)分步計(jì)數(shù)原理裝球的方法共有_____解決排列組合混合問題,先選后排是最基本的指導(dǎo)思想.此法與相鄰元素捆綁策略相似嗎?第18頁(yè),共34頁(yè),2023年,2月20日,星期四練習(xí)題一個(gè)班有6名戰(zhàn)士,其中正副班長(zhǎng)各1人現(xiàn)從中選4人完成四種不同的任務(wù),每人完成一種任務(wù),且正副班長(zhǎng)有且只有1人參加,則不同的選法有______種第19頁(yè),共34頁(yè),2023年,2月20日,星期四十.小集團(tuán)問題先整體后局部策略例9.用1,2,3,4,5組成沒有重復(fù)數(shù)字的五位數(shù)其中恰有兩個(gè)偶數(shù)夾1,5這兩個(gè)奇數(shù)之間,這樣的五位數(shù)有多少個(gè)?解:把1,5,2,4當(dāng)作一個(gè)小集團(tuán)與3排隊(duì)共有____種排法,再排小集團(tuán)內(nèi)部共有

_______種排法,由分步計(jì)數(shù)原理共有

_______種排法.31245小集團(tuán)小集團(tuán)排列問題中,先整體后局部,再結(jié)合其它策略進(jìn)行處理。第20頁(yè),共34頁(yè),2023年,2月20日,星期四1.計(jì)劃展出10幅不同的畫,其中1幅水彩畫,4幅油畫,5幅國(guó)畫,排成一行陳列,要求同一品種的必須連在一起,并且水彩畫不在兩端,那么共有陳列方式的種數(shù)為_______2.5男生和5女生站成一排照像,男生相鄰,女生也相鄰的排法有_______種第21頁(yè),共34頁(yè),2023年,2月20日,星期四十一.元素相同問題隔板策略例10.有10個(gè)運(yùn)動(dòng)員名額,在分給7個(gè)班,每班至少一個(gè),有多少種分配方案?

解:因?yàn)?0個(gè)名額沒有差別,把它們排成一排。相鄰名額之間形成9個(gè)空隙。在9個(gè)空檔中選6個(gè)位置插個(gè)隔板,可把名額分成7份,對(duì)應(yīng)地分給7個(gè)班級(jí),每一種插板方法對(duì)應(yīng)一種分法共有___________種分法。一班二班三班四班五班六班七班將n個(gè)相同的元素分成m份(n,m為正整數(shù)),每份至少一個(gè)元素,可以用m-1塊隔板,插入n個(gè)元素排成一排的n-1個(gè)空隙中,所有分法數(shù)為第22頁(yè),共34頁(yè),2023年,2月20日,星期四練習(xí)題10個(gè)相同的球裝5個(gè)盒中,每盒至少一個(gè),有多少裝法?第23頁(yè),共34頁(yè),2023年,2月20日,星期四十二.平均分組問題除法策略例12.6本不同的書平均分成3堆,每堆2本共有多少分法?解:分三步取書得種方法,但這里出現(xiàn)重復(fù)計(jì)數(shù)的現(xiàn)象,不妨記6本書為ABCDEF

若第一步取AB,第二步取CD,第三步取EF

該分法記為(AB,CD,EF),則中還有

(AB,EF,CD),(CD,AB,EF),(CD,EF,AB)(EF,CD,AB),(EF,AB,CD)共有種取法,而這些分法僅是(AB,CD,EF)一種分法,故共有種分法。平均分成的組,不管它們的順序如何,都是一種情況,所以分組后要一定要除以(n為均分的組數(shù))避免重復(fù)計(jì)數(shù)。第24頁(yè),共34頁(yè),2023年,2月20日,星期四1將13個(gè)球隊(duì)分成3組,一組5個(gè)隊(duì),其它兩組4

個(gè)隊(duì),有多少分法?2.某校高二年級(jí)共有六個(gè)班級(jí),現(xiàn)從外地轉(zhuǎn)入4名學(xué)生,要安排到該年級(jí)的兩個(gè)班級(jí)且每班安排2名,則不同的安排方案種數(shù)為______

第25頁(yè),共34頁(yè),2023年,2月20日,星期四十三.構(gòu)造模型策略例14.馬路上有編號(hào)為1,2,3,4,5,6,7,8,9的九只路燈,現(xiàn)要關(guān)掉其中的3盞,但不能關(guān)掉相鄰的2盞或3盞,也不能關(guān)掉兩端的2

盞,求滿足條件的關(guān)燈方法有多少種?解:把此問題當(dāng)作一個(gè)排隊(duì)模型在6盞亮燈的5個(gè)空隙中插入3個(gè)不亮的燈有________種一些不易理解的排列組合題如果能轉(zhuǎn)化為非常熟悉的模型,如占位填空模型,排隊(duì)模型,裝盒模型等,可使問題直觀解決第26頁(yè),共34頁(yè),2023年,2月20日,星期四練習(xí)題某排共有10個(gè)座位,若4人就坐,每人左右兩邊都有空位,那么不同的坐法有多少種?第27頁(yè),共34頁(yè),2023年,2月20日,星期四十四.實(shí)際操作窮舉策略例15.設(shè)有編號(hào)1,2,3,4,5的五個(gè)球和編號(hào)1,23,4,5的五個(gè)盒子,現(xiàn)將5個(gè)球投入這五個(gè)盒子內(nèi),要求每個(gè)盒子放一個(gè)球,并且恰好有兩個(gè)球的編號(hào)與盒子的編號(hào)相同,.

有多少投法

解:從5個(gè)球中取出2個(gè)與盒子對(duì)號(hào)有_____種還剩下3球3盒序號(hào)不能對(duì)應(yīng),利用實(shí)際操作法,如果剩下3,4,5號(hào)球,3,4,5號(hào)盒3號(hào)球裝4號(hào)盒時(shí),則4,5號(hào)球有只有1種裝法3號(hào)盒4號(hào)盒5號(hào)盒345第28頁(yè),共34頁(yè),2023年,2月20日,星期四十四.實(shí)際操作窮舉策略例15.設(shè)有編號(hào)1,2,3,4,5的五個(gè)球和編號(hào)1,23,4,5的五個(gè)盒子,現(xiàn)將5個(gè)球投入這五個(gè)盒子內(nèi),要求每個(gè)盒子放一個(gè)球,并且恰好有兩個(gè)球的編號(hào)與盒子的編號(hào)相同,.

有多少投法

解:從5個(gè)球中取出2個(gè)與盒子對(duì)號(hào)有_____種還剩下3球3盒序號(hào)不能對(duì)應(yīng),利用實(shí)際操作法,如果剩下3,4,5號(hào)球,3,4,5號(hào)盒3號(hào)球裝4號(hào)盒時(shí),則4,5號(hào)球有只有1種裝法,

同理3號(hào)球裝5號(hào)盒時(shí),4,5號(hào)球有也只有1種裝法,由分步計(jì)數(shù)原理有2種

第29頁(yè),共34頁(yè),2023年,2月20日,星期四對(duì)于條件比較復(fù)雜的排列組合問題,不易用公式進(jìn)行運(yùn)算,往往利用窮舉法或畫出樹狀圖會(huì)收到意想不到的結(jié)果練習(xí)題同一寢室4人,每人寫一張賀年卡集中起來,

然后每人各拿一張別人的賀年卡,則四張賀年卡不同的分配方式有多少種?(9)1A2B3C4D1A1B1C1D2A2B2C2D3A3B3C3D4A4B4C4D1B2A3D4C1B2C3D4A1B2D3A4C第30頁(yè),共34頁(yè),2023年,2月20日,星期四十五.分解與合成策略例16.30030能被多少個(gè)不同的偶數(shù)整除分析:先把30030分解成質(zhì)因數(shù)的乘積形式

30030=2×3×5×7×11×13依題意可知偶因數(shù)必先取2,再?gòu)钠溆?個(gè)因數(shù)中任取若干個(gè)組成乘積

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論