解排列組合問題的十八種常用策略.ppt

解排列組合問題的十七種常用策略 一 特殊元素和特殊位置優(yōu)先策略 例1 由0 1 2 3 4 5可以組成多少個(gè)沒有重復(fù)數(shù)字五位奇數(shù) 解 由于末位和首位有特殊要求 應(yīng)該優(yōu)先安排 以免不合要求的元素占了這兩個(gè)位置 先排末位共有 然后排首位共有 最后排其它位置共有 位置分析法和元素分析法是解決排列組合問題最常用也是最基本的方法 若以元素分析為主 需先安排特殊元素 再處理其它元素 若以位置分析為主 需先滿足特殊位置的要求 再處理其它位置 若有多個(gè)約束條件 往往是考慮一個(gè)約束條件的同時(shí)還要兼顧其它條件 7種不同的花種在排成一列的花盆里 若兩種葵花不種在中間 也不種在兩端的花盆里 問有多少不同的種法 練習(xí)題 二 相鄰元素捆綁策略 例2 7人站成一排 其中甲乙相鄰且丙丁相鄰 共有多少種不同的排法 解 可先將甲乙兩元素捆綁成整體并看成一個(gè)復(fù)合元素 同時(shí)丙丁也看成一個(gè)復(fù)合元素 再與其它元素進(jìn)行排列 同時(shí)對(duì)相鄰元素內(nèi)部進(jìn)行自排 要求某幾個(gè)元素必須排在一起的問題 可以用捆綁法來解決問題 即將需要相鄰的元素合并為一個(gè)元素 再與其它元素一起作排列 同時(shí)要注意合并元素內(nèi)部也必須排列 某人射擊8槍 命中4槍 4槍命中恰好有3槍連在一起的情形的不同種數(shù)為 練習(xí)題 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ú)唱共有種 元素相離問題可先把沒有位置要求的元素進(jìn)行排隊(duì)再把不相鄰元素插入中間和兩端 某班新年聯(lián)歡會(huì)原定的5個(gè)節(jié)目已排成節(jié)目單 開演前又增加了兩個(gè)新節(jié)目 如果將這兩個(gè)新節(jié)目插入原節(jié)目單中 且兩個(gè)新節(jié)目不相鄰 那么不同插法的種數(shù)為 30 練習(xí)題 四 定序問題倍縮空位插入策略 例4 7人排隊(duì) 其中甲乙丙3人順序一定共有多少不同的排法 解 倍縮法 對(duì)于某幾個(gè)元素順序一定的排列問題 可先把這幾個(gè)元素與其他元素一起進(jìn)行排列 然后用總排列數(shù)除以這幾個(gè)元素之間的全排列數(shù) 則共有不同排法種數(shù)是 空位法 設(shè)想有7把椅子讓除甲乙丙以外的四人就坐共有種方法 其余的三個(gè)位置甲乙丙共有種坐法 則共有種方法 1 思考 可以先讓甲乙丙就坐嗎 插入法 先排甲乙丙三個(gè)人 共有1種排法 再把其余4四人依次插入共有方法 4 5 6 7 定序問題可以用倍縮法 還可轉(zhuǎn)化為占位插空模型處理 練習(xí)題 10人身高各不相等 排成前后排 每排5人 要求從左至右身高逐漸增加 共有多少排法 五 重排問題求冪策略 例5 把6名實(shí)習(xí)生分配到7個(gè)車間實(shí)習(xí) 共有多少種不同的分法 解 完成此事共分六步 把第一名實(shí)習(xí)生分配到車間有種分法 7 1 某班新年聯(lián)歡會(huì)原定的5個(gè)節(jié)目已排成節(jié)目單 開演前又增加了兩個(gè)新節(jié)目 如果將這兩個(gè)節(jié)目插入原節(jié)目單中 那么不同插法的種數(shù)為 42 2 某8層大樓一樓電梯上來8名乘客人 他們到各自的一層下電梯 下電梯的方法 練習(xí)題 六 環(huán)排問題線排策略 例6 5人圍桌而坐 共有多少種坐法 解 圍桌而坐與坐成一排的不同點(diǎn)在于 坐成圓形沒有首尾之分 所以固定一人A并從此位置把圓形展成直線其余4人共有 種排法即 5 1 一般地 n個(gè)不同元素作圓形排列 共有 n 1 種排法 如果從n個(gè)不同元素中取出m個(gè)元素作圓形排列共有 練習(xí)題 6顆顏色不同的鉆石 可穿成幾種鉆石圈 60 七 多排問題直排策略 例7 8人排成前后兩排 每排4人 其中甲乙在前排 丁在后排 共有多少排法 解 8人排前后兩排 相當(dāng)于8人坐8把椅子 可以把椅子排成一排 一般地 元素分成多排的排列問題 可歸結(jié)為一排考慮 再分段研究 有兩排座位 前排11個(gè)座位 后排12個(gè)座位 現(xiàn)安排2人就座規(guī)定前排中間的3個(gè)座位不能坐 并且這2人不左右相鄰 那么不同排法的種數(shù)是 346 練習(xí)題 八 排列組合混合問題先選后排策略 例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)思想 此法與相鄰元素捆綁策略相似嗎 練習(xí)題 一個(gè)班有6名戰(zhàn)士 其中正副班長(zhǎng)各1人現(xiàn)從中選4人完成四種不同的任務(wù) 每人完成一種任務(wù) 且正副班長(zhǎng)有且只有1人參加 則不同的選法有 種 192 九 小集團(tuán)問題先整體局部策略 例9 用1 2 3 4 5組成沒有重復(fù)數(shù)字的五位數(shù)其中恰有兩個(gè)偶數(shù)夾1 這兩個(gè)奇數(shù)之間 這樣的五位數(shù)有多少個(gè) 解 把 當(dāng)作一個(gè)小集團(tuán)與 排隊(duì)共有 種排法 再排小集團(tuán)內(nèi)部共有 種排法 由分步計(jì)數(shù)原理共有 種排法 小集團(tuán)排列問題中 先整體后局部 再結(jié)合其它策略進(jìn)行處理 計(jì)劃展出10幅不同的畫 其中1幅水彩畫 幅油畫 幅國(guó)畫 排成一行陳列 要求同一品種的必須連在一起 并且水彩畫不在兩端 那么共有陳列方式的種數(shù)為 2 5男生和 女生站成一排照像 男生相鄰 女生也相鄰的排法有 種 十 元素相同問題隔板策略 例10 有10個(gè)運(yùn)動(dòng)員名額 在分給7個(gè)班 每班至少一個(gè) 有多少種分配方案 解 因?yàn)?0個(gè)名額沒有差別 把它們排成一排 相鄰名額之間形成 個(gè)空隙 在 個(gè)空檔中選 個(gè)位置插個(gè)隔板 可把名額分成 份 對(duì)應(yīng)地分給 個(gè)班級(jí) 每一種插板方法對(duì)應(yīng)一種分法共有 種分法 將n個(gè)相同的元素分成m份 n m為正整數(shù) 每份至少一個(gè)元素 可以用m 1塊隔板 插入n個(gè)元素排成一排的n 1個(gè)空隙中 所有分法數(shù)為 練習(xí)題 10個(gè)相同的球裝5個(gè)盒中 每盒至少一個(gè) 有多少裝法 2 x y z w 100求這個(gè)方程組的自然數(shù)解的組數(shù) 十一 正難則反總體淘汰策略 例11 從0 1 2 3 4 5 6 7 8 9這十個(gè)數(shù)字中取出三個(gè)數(shù) 使其和為不小于10的偶數(shù) 不同的取法有多少種 解 這問題中如果直接求不小于10的偶數(shù)很困難 可用總體淘汰法 再淘汰和小于10的偶數(shù)共 符合條件的取法共有 9 有些排列組合問題 正面直接考慮比較復(fù)雜 而它的反面往往比較簡(jiǎn)捷 可以先求出它的反面 再?gòu)恼w中淘汰 我們班里有43位同學(xué) 從中任抽5人 正 副班長(zhǎng) 團(tuán)支部書記至少有一人在內(nèi)的抽法有多少種 練習(xí)題 十二 平均分組問題除法策略 例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ù) 1將13個(gè)球隊(duì)分成3組 一組5個(gè)隊(duì) 其它兩組4個(gè)隊(duì) 有多少分法 2 10名學(xué)生分成3組 其中一組4人 另兩組3人但正副班長(zhǎng)不能分在同一組 有多少種不同的分組方法 1540 3 某校高二年級(jí)共有六個(gè)班級(jí) 現(xiàn)從外地轉(zhuǎn)入4名學(xué)生 要安排到該年級(jí)的兩個(gè)班級(jí)且每班安排2名 則不同的安排方案種數(shù)為 十三 合理分類與分步策略 例13 在一次演唱會(huì)上共10名演員 其中8人能能唱歌 5人會(huì)跳舞 現(xiàn)要演出一個(gè)2人唱歌2人伴舞的節(jié)目 有多少選派方法 解 10演員中有5人只會(huì)唱歌 2人只會(huì)跳舞3人為全能演員 本題還有如下分類標(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)一旦確定要貫穿于解題過程的始終 1 從4名男生和3名女生中選出4人參加某個(gè)座談會(huì) 若這4人中必須既有男生又有女生 則不同的選法共有 34 練習(xí)題 2 3成人2小孩乘船游玩 1號(hào)船最多乘3人 2號(hào)船最多乘2人 3號(hào)船只能乘1人 他們?nèi)芜x2只船或3只船 但小孩不能單獨(dú)乘一只船 這3人共有多少乘船方法 27 十四 構(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ì)模型 裝盒模型等 可使問題直觀解決 練習(xí)題 某排共有10個(gè)座位 若4人就坐 每人左右兩邊都有空位 那么不同的坐法有多少種 120 十五 實(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í)際操作窮舉策略 例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) 同理3號(hào)球裝5號(hào)盒時(shí) 4 5號(hào)球有也只有1種裝法 由分步計(jì)數(shù)原理有2種 對(duì)于條件比較復(fù)雜的排列組合問題 不易用公式進(jìn)行運(yùn)算 往往利用窮舉法或畫出樹狀圖會(huì)收到意想不到的結(jié)果 練習(xí)題 同一寢室4人 每人寫一張賀年卡集中起來 然后每人各拿一張別人的賀年卡 則四張賀年卡不同的分配方式有多少種 9 2 給圖中區(qū)域涂色 要求相鄰區(qū)域不同色 現(xiàn)有4種可選顏色 則不同的著色方法有 種 72 十六 分解與合成策略 例16 30030能被多少個(gè)不同的偶數(shù)整除 分析 先把30030分解成質(zhì)因數(shù)的乘積形式30030 2 3 5 7 11 13依題意可知偶因數(shù)必先取2 再?gòu)钠溆?個(gè)因數(shù)中任取若干個(gè)組成乘積 所有的偶因數(shù)為 例17 正方體的8個(gè)頂點(diǎn)可連成多少對(duì)異面直線 解 我們先從8個(gè)頂點(diǎn)中任取4個(gè)頂點(diǎn)構(gòu)成四體共有體共 6 6 58 174 分解與合成策略是排列組合問題的一種最基本的解題策略 把一個(gè)復(fù)雜問題分解成幾個(gè)小問題逐一解決 然后依據(jù)問題分解后的結(jié)構(gòu) 用分類計(jì)數(shù)原理和分步計(jì)數(shù)原理將問題合成 從而得到問題的答案 每個(gè)比較復(fù)雜的問題都要用到這種解題策略 十七 化歸策略 例18 25人排成5 5方隊(duì) 現(xiàn)從中選3人 要求3人不在同一行也不在同一列 不同的選法有多少種 解 將這個(gè)問題退化成9人排成3 3方隊(duì) 現(xiàn)從中選3人 要求3人不在同一行也不在同一列 有多少選法 這樣每行必有1人從