《排列组合涂色问题技巧 2012解决排列组合问题的常用技巧与策略》由会员分享,可在线阅读,更多相关《排列组合涂色问题技巧 2012解决排列组合问题的常用技巧与策略(19页珍藏版)》请在金锄头文库上搜索。
1、1排列组合涂色问题技巧排列组合涂色问题技巧 20122012 解决排列组合问题的解决排列组合问题的 常用技巧与策略常用技巧与策略导读:就爱阅读网友为您分享以下导读:就爱阅读网友为您分享以下“2012 解决排列组合解决排列组合问题的常用技巧与策略问题的常用技巧与策略”的资讯,希望对您有所帮助,感谢的资讯,希望对您有所帮助,感谢您对您对 的支持的支持!解决排列组合问题的常用技巧与策略解决排列组合问题的常用技巧与策略 解排列组合问题是每年高考必考的内容,因此解题要讲解排列组合问题是每年高考必考的内容,因此解题要讲究策略,首先要认真审题,弄清楚是排列究策略,首先要认真审题,弄清楚是排列(有序有序)还
2、是组合还是组合(无序无序),还是排列与组合混合问题。其次,要抓住问题的本,还是排列与组合混合问题。其次,要抓住问题的本质特征,准确合理地利用两个基本原则进行质特征,准确合理地利用两个基本原则进行“分类与分步分类与分步”。加法原理的特征是分类解决问题,分类必须满足两个条件:加法原理的特征是分类解决问题,分类必须满足两个条件:类与类必须互斥类与类必须互斥(不相容不相容),总类必须完备总类必须完备(不遗漏不遗漏);乘;乘法原理的特征是分步解决问题,分步必须做到步与步互相法原理的特征是分步解决问题,分步必须做到步与步互相独立,互不干扰并确保连续性。分类与分步是解决排列组独立,互不干扰并确保连续性。分类
3、与分步是解决排列组合问题的最基本的思想策略,在实际操作中往往是合问题的最基本的思想策略,在实际操作中往往是“步步”与与2“类类”交叉,有机结合,可以是类中有步,也可以是步中有交叉,有机结合,可以是类中有步,也可以是步中有类。类。 以上解题思路分析,可以用顺口溜概括为:以上解题思路分析,可以用顺口溜概括为:“十六字方十六字方针,十二个技巧针,十二个技巧” 1、 “十六字方针十六字方针”是解排列组合问题的规律,即分类相加、是解排列组合问题的规律,即分类相加、分步相乘、有序排列、无序组合。分步相乘、有序排列、无序组合。 2、 “十二个技巧十二个技巧”是速解是速解排列组合题的捷径,即排列组合题的捷径,
4、即相邻问题捆绑法;相邻问题捆绑法;不相邻问题不相邻问题插空法;插空法;多排问题单排法;多排问题单排法;定序问题倍缩法;定序问题倍缩法;定位定位问题优先法;问题优先法;有序分配问题分步法有序分配问题分步法多元问题分类法;多元问题分类法;交叉问题集合法;交叉问题集合法;至少(或至多)问题间接法;至少(或至多)问题间接法;选选排问题先取后排法;排问题先取后排法;11 局部与整体问题排除法;局部与整体问题排除法;12 复杂复杂问题转化法。问题转化法。 一一.特殊元素的特殊元素的“优先安排法优先安排法” 对于特殊元素的排列组合问题,一般先考虑特殊元素,对于特殊元素的排列组合问题,一般先考虑特殊元素,再考
5、虑其他元素的安排。在操作时,针对实际问题,有时再考虑其他元素的安排。在操作时,针对实际问题,有时“元素优先元素优先”,有时,有时“位置优先位置优先”。 例例 1 0、2、3、4、5 这五个数字,组成没有重复数字的这五个数字,组成没有重复数字的三位数,其中偶数共有几个?三位数,其中偶数共有几个? 11 解法一:解法一:(元素优先元素优先)分两类:第一类,含分两类:第一类,含 0,0 在个位在个位有有 A24 种,种,0 在十位有在十位有 A2A3 种;种; 221112 第二类,不含第二类,不含 0,有,有 A12A3 种。种。 故共有(故共有( A4A2A3)A2A3种。种。 注:在考虑每一类
6、时,又要优先考虑个位。注:在考虑每一类时,又要优先考虑个位。 3解法二:解法二:(位置优先位置优先)分两类:第一类,分两类:第一类,0 在个位有在个位有 A24 种;种;第二类,第二类,0 不在个位,先从两个偶数不在个位,先从两个偶数 中选一个放个位,再中选一个放个位,再选一个放百位,最后考虑十位,有选一个放百位,最后考虑十位,有 二排除法(总体淘汰二排除法(总体淘汰法)法) 对于含有否定词语的问题,还可以从总体中把不符合要对于含有否定词语的问题,还可以从总体中把不符合要求的除去,此时应注意既不能多求的除去,此时应注意既不能多 减也不能少减,例如在例减也不能少减,例如在例中也可以用此法解答:个
7、数字组成三位数的全排列为中也可以用此法解答:个数字组成三位数的全排列为A35,排好后发现不能在首位,而且和不能排在末尾,排好后发现不能在首位,而且和不能排在末尾,这两种不合题意的排法要除去,故有个偶数这两种不合题意的排法要除去,故有个偶数 种。种。 故共有故共有 三多元问题分类法(合理分类与准确分步)三多元问题分类法(合理分类与准确分步) 解含有约束条件的排列组合问题,应按元素的性质进行解含有约束条件的排列组合问题,应按元素的性质进行分类,事情的发生的连续过程分步,做到分类标准明确,分类,事情的发生的连续过程分步,做到分类标准明确,分步层次清楚,不重不漏分步层次清楚,不重不漏 例:个人从左到右
8、站成一排,甲不站排头,乙不站例:个人从左到右站成一排,甲不站排头,乙不站第二个位置,不同的站法有第二个位置,不同的站法有 解:由题意,可先解:由题意,可先安排甲,并按其进行分类讨论:安排甲,并按其进行分类讨论: (1)若甲在第二个位置上,则剩下的其余四人可自由安)若甲在第二个位置上,则剩下的其余四人可自由安排,有排,有 A44 种方法;种方法; 13(2)若甲在第三个或第四、五个位置上,则根据分步)若甲在第三个或第四、五个位置上,则根据分步计数原理不同的站法有计数原理不同的站法有 A13A3A3 种站法;种站法; 4113 再根据分类计数原理,不同的站法共有:再根据分类计数原理,不同的站法共有
9、:A44A3A3A3种种 四四.相邻问题:捆绑法相邻问题:捆绑法 对于某些元素要求相邻排列的问题,可先将相邻元素捆对于某些元素要求相邻排列的问题,可先将相邻元素捆绑成整体并看作一个元素再与其绑成整体并看作一个元素再与其 它元素进行排列,同时它元素进行排列,同时对相邻元素内部进行自排。对相邻元素内部进行自排。 例例 3: 5 个男生个男生 3 个女生排成一列,要求女生排一起,个女生排成一列,要求女生排一起,共有几种排法?共有几种排法? 解:先把解:先把 3 个女生捆绑为一个整体再与其他个女生捆绑为一个整体再与其他 5 个男生全个男生全排列。同时,排列。同时,3 个女生自身也应全排列。个女生自身也
10、应全排列。3 由乘法原理共有由乘法原理共有 A66A5 种。种。 五、不相邻问题用五、不相邻问题用“插空法插空法” 对于某几个元素不相邻的排列问题,可先将其他元素排对于某几个元素不相邻的排列问题,可先将其他元素排好,再将不相邻的元素在已排好的元素之间及两端的空隙好,再将不相邻的元素在已排好的元素之间及两端的空隙之间插入即可(注意有时候两端的空隙的插法是不符合题之间插入即可(注意有时候两端的空隙的插法是不符合题意的)意的). 例例 4: 5 个男生个男生 3 个女生排成一列,要求女生不个女生排成一列,要求女生不相邻且不可排两头,共有几种排法?相邻且不可排两头,共有几种排法? 3 解:先排无限制条
11、件的男生,女生插在解:先排无限制条件的男生,女生插在 5 个男生间的个男生间的 4个空隙,由乘法原理共有个空隙,由乘法原理共有 A55A4 种。种。 注意:注意:分清分清“谁插入谁谁插入谁”的问题。要先排无限制条件的的问题。要先排无限制条件的元素,再插入必须间隔的元素;元素,再插入必须间隔的元素; 数清可插的位置数清可插的位置数;数;插入时是以组合形式插入还是以排列形式插入要把插入时是以组合形式插入还是以排列形式插入要把5握准。握准。 例例 5: 马路上有编号为马路上有编号为 1、2、3、?、9 的的 9 盏路盏路灯,现要关掉其中的三盏,但不能同灯,现要关掉其中的三盏,但不能同 时关掉相邻的两
12、时关掉相邻的两盏或三盏,也不能关两端的路灯,则满足要求的关灯方法盏或三盏,也不能关两端的路灯,则满足要求的关灯方法有几种?有几种? 解:由于问题中有解:由于问题中有 6 盏亮盏亮 3 盏暗,又两端不可盏暗,又两端不可暗,故可在暗,故可在 6 盏亮的盏亮的 5 个间隙中插入个间隙中插入 3 个个 暗的即可,暗的即可,有有 C35 种。种。 六、定序问题倍缩法(顺序固定问题用先排后除或选位六、定序问题倍缩法(顺序固定问题用先排后除或选位不排或先定后插)不排或先定后插) 对于某几个元素顺序一定的排列问题,可先把这几个元对于某几个元素顺序一定的排列问题,可先把这几个元素与其他元素一起进行排列,然后用总
13、排列数除以这几个素与其他元素一起进行排列,然后用总排列数除以这几个元素之间的全排列数。或先在总位置中选出顺序一定元素元素之间的全排列数。或先在总位置中选出顺序一定元素的位置而不参加排列,然后对其它元素进行排列。也可先的位置而不参加排列,然后对其它元素进行排列。也可先放好顺序一定元素,再一一插入其它元素。放好顺序一定元素,再一一插入其它元素。 例例 6: 5 人人参加百米跑,若无同时到达终点的情况,则甲比乙先到有参加百米跑,若无同时到达终点的情况,则甲比乙先到有几种情况?几种情况? 2 解法一:先解法一:先 5 人全排有人全排有 A55 种,由于全排中有甲、乙种,由于全排中有甲、乙的全排种数的全
14、排种数 A2,而这里只有,而这里只有 1 种是种是 52 符合要求的,符合要求的,故要除以定序元素的全排列故要除以定序元素的全排列 A22 种,所以有种,所以有 A5 /A2 =60 种。种。2 解法二:先在解法二:先在 5 个位置中选个位置中选 2 个位置放定序元素个位置放定序元素(甲、甲、乙乙)有有 C5 种,再排列其它种,再排列其它 3 人有人有 A33, 2 由乘法原理由乘法原理得共有得共有 C5A33 =60 种。种。 解法三:先固定甲、乙,再插入另三个中的第一人有解法三:先固定甲、乙,再插入另三个中的第一人有 36种方法,接着插入第二人有种方法,接着插入第二人有 4 种种 方法,最
15、后插入第三方法,最后插入第三人有人有 5 种方法。由乘法原理得共有种方法。由乘法原理得共有 七、选排问题先取后排。七、选排问题先取后排。(“小团体小团体”排列,先排列,先“团体团体”后整体)后整体) 对于某些排列问题中的某些元素要求组成对于某些排列问题中的某些元素要求组成“小团体小团体”时,时,可先按制约条件可先按制约条件“组团组团”并视为一个元素再与其它元素排列。并视为一个元素再与其它元素排列。例例 7:四名男歌手与两名女歌手联合举行一场演唱会,演四名男歌手与两名女歌手联合举行一场演唱会,演出的出场顺序要求两名女歌手之出的出场顺序要求两名女歌手之 间有两名男歌手,则间有两名男歌手,则出场方案
16、有几种?出场方案有几种? 2 解:先从四名男歌手中选解:先从四名男歌手中选 2 人排入两女歌手之间进行人排入两女歌手之间进行“组团组团”有有 A2A42 种,把这个种,把这个“女男男女女男男女”223 小团体视为小团体视为 1 人再与其余人再与其余 2 男进行排列有男进行排列有 A33 种,种,由乘法原理,共有由乘法原理,共有 A4A2A3 种种 =60 种。种。 八、交叉问题八、交叉问题集合法集合法 例例 8、从、从 6 名运动员中先出名运动员中先出 4 人参加人参加 4100m 接力赛,接力赛,如果甲不跑第一棒,乙不跑第四棒,共有如果甲不跑第一棒,乙不跑第四棒,共有多少种不同的参赛方法。多少种不同的参赛方法。 解:解:6 人任选人任选