《{战略管理}解排列组合问题的十七种常用策略》由会员分享，可在线阅读，更多相关《{战略管理}解排列组合问题的十七种常用策略（118页珍藏版）》请在金锄头文库上搜索。
1、,解排列组合问题的常用策略,排列组合应用题解法综述（目录）,基本概念和考点,合理分类和准确分步,特殊元素和特殊位置问题,相邻相间问题,定序问题,分房问题,环排、多排问题,小集团问题,先选后排问题,平均分组问题,构造模型策略,实验法（枚举法）,其它特殊方法,排列组合应用题解法综述,计数问题中排列组合问题是最常见的，由于其解法往往是构造性的, 因此方法灵活多样, 不同解法导致问题难易变化也较大，而且解题过程出现“重复”和“遗漏”的错误较难自检发现。因而对这类问题归纳总结，并把握一些常见解题模型是必要的。,回目录,基 本 原 理,组合,排列,排列数公式,组合数公式,组合数性质,应 用 问 题,知识结
2、构网络图：,回目录,两个原理的区别与联系：,做一件事或完成一项工作的方法数,直接（分类）完成,间接（分步骤）完成,做一件事，完成它可以有n类办法， 第一类办法中有m1种不同的方法， 第二类办法中有m2种不同的方法， 第n类办法中有mn种不同的方法， 那么完成这件事共有 N=m1+m2+m3+mn 种不同的方法,做一件事，完成它可以有n个步骤， 做第一步中有m1种不同的方法， 做第二步中有m2种不同的方法， 做第n步中有mn种不同的方法， 那么完成这件事共有 N=m1m2m3mn 种不同的方法.,回目录,1.排列和组合的区别和联系：,从n个不同元素中取出m个元 素，按一定的顺序排成一列,从n个不
3、同元素中取出m个元 素，把它并成一组,所有排列的的个数,所有组合的个数,回目录,2.掌握解决排列组合问题的常用策略;能运 用解题策略解决简单的综合应用题。提高学生解决问题分析问题的能力,3.学会应用数学思想和方法解决排列组合问题.,教学目标,1.进一步理解和应用分步计数原理和分类计数原理。,回目录,完成一件事，有n类办法，在第1类办法中有 m1种不同的方法，在第2类办法中有m2 种不同的方法，在第n类办法中有mn种不同的方法，那么完成这件事共有： 种不同的方法,1.分类计数原理(加法原理),回目录,完成一件事，需要分成n个步骤，做第1步有m1种不同的方法，做第2步有m2 种不同的方法，做第n步
4、有mn种不同的方法，那么完成这件事共有： 种不同的方法,2.分步计数原理（乘法原理）,分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件,3.分类计数原理分步计数原理区别,分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。,回目录,某校组织学生分4个组从3处风景点中选一处去春游,则不同的春游方案的种数是 A. B. C. D.,（ 选 C）,回目录,将数字1、2、3、4 填入标号为1、2、3、4 的四个方格里 , 每格填一个数字，则每个方格的标号与所填的数字都不相同的填法共有 A. 6 种 B. 9种 C.11种 D.23种,（ 331= 9. 可用框图具体
5、填写）,回目录,考点分析,从考纲大纲看：高考对这部分的要求还是比较高的.要重视两个计数原理、排列、组合在解决实际问题上的应用.值得提醒地是：计数模型不一定是排列或组合.画一画，数一数，算一算，是基本的计数方法，不可废弃. 例（2001年新课程卷） 某赛季足球比赛的计分规则是：胜一场，得3分；平一场，得1分；负一场，得0分.一球队打完15场，积33分.若不考虑顺序，该队胜、负、平的情况共有 A 3种 B 4种 C 5种 D 6种.,回目录,解决排列组合综合性问题的一般过程如下:,1.认真审题弄清要做什么事,2.怎样做才能完成所要做的事,即采取分步还 是分类,或是分步与分类同时进行,确定分多 少步
6、及多少类。,3.确定每一步或每一类是排列问题(有序)还是 组合(无序)问题,元素总数是多少及取出多 少个元素.,解决排列组合综合性问题，往往类与步交 叉，因此必须掌握一些常用的解题策略,回目录,判断下列问题是组合问题还是排列问题?,(1)设集合A=a,b,c,d,e，则集合A的含有 3个元素的子集有多少个?,(2)某铁路线上有5个车站，则这条铁路线上 共需准备多少种车票?,有多少种不同的火车票价？,组合问题,排列问题,(3)10名同学分成人数相同的数学和 英语两个学习小组，共有多少种分法?,组合问题,(4)10人聚会，见面后每两人之间要 握手相互问候，共需握手多少次?,组合问题,(5)从4个风
7、景点中选出2个安排游览, 有多少种不同的方法?,组合问题,(6)从4个风景点中选出2个,并确定这2个风景 点的游览顺序,有多少种不同的方法?,排列问题,组合问题,回目录,合理分类和准确分步,解排列（或）组合问题，应按元素的性质进行分类，分类标准明确，不重不漏；按事情的发生的连续过程分步，做到分步层次清楚.,回目录,总的原则合理分类和准确分步,解排列（或）组合问题，应按元素的性质进行分类，事情的发生的连续过程分步，做到分类标准明确，分步层次清楚，不重不漏。,解法1 分析：先安排甲，按照要求对其进行分类，分两类：,根据分步及分类计数原理，不同的站法共有,例1 6个同学和2个老师排成一排照相， 2个
8、老师站中间，学生甲不站排头，学生乙不站排尾，共有多少种不同的排法？,1）若甲在排尾上，则剩下的5人可自由安排，有 种方法.,若甲在第2、3、6、7位，则排尾的排法有 种，1位的排法有 种, 第2、3、6、7位的排法有 种，根据分步计数原理，不同的站法有 种。,再安排老师，有2种方法。,回目录,把握分类原理、分步原理是基础 例1 如图，某电子器件是由三个电 阻组成的回路,其中有6个焊接 点A，B，C，D，E，F，如果某个焊接点脱落，整个电路就会不通。现发现电路不通了, 那么焊接点脱落的可能性共有（ ） 63种 （B）64种 （C）6种 （D）36种,分析:由加法原理可知,由乘法原理可知 2222
9、22-1=63,回目录,（1）0，1，2，3，4，5可组成多少个无重复数字且能被五整除的五位数？,练 习 1,分类：个位数字为5或0：,个位数为0：,个位数为5：,回目录,（2）0，1，2，3，4，5可组成多少个无重复数字且大于31250的五位数？,分类：,引申1：31250是由0，1，2，3，4，5组成的无重复数字的五位数中从小到大第几个数？,方法一：（排除法）,方法二：（直接法）,引申2：由0，1，2，3，4，5组成的无重复数字的 五位数中大于31250，小于50124的数共有多少个？,2004 全国12 在由数字1，2，3，4，5组成的所有 没有重复的5位数中，大于23145且小于435
10、12的 数共有（ ）个,58,回目录,合理分类与分步策略,例.在一次演唱会上共10名演员,其中8人能 能唱歌,5人会跳舞,现要演出一个2人 唱歌2人伴舞的节目,有多少选派方法?,解：,10演员中有5人只会唱歌，2人只会跳舞 3人为全能演员。,回目录,本题还有如下分类标准： *以3个全能演员是否选上唱歌人员为标准 *以3个全能演员是否选上跳舞人员为标准 *以只会跳舞的2人是否选上跳舞人员为标准 都可经得到正确结果,解含有约束条件的排列组合问题，可按元素 的性质进行分类，按事件发生的连续过程分 步，做到标准明确。分步层次清楚，不重不 漏，分类标准一旦确定要贯穿于解题过程的 始终。,回目录,有不同的
11、数学书7本，语文书5本，英语书4本，由其中取出不是同一学科的书2本，共有多少种不同的取法？,（75 + 74 + 54 = 83）,回目录,（4）（2005福建理）从6人中选4人分别到巴黎、伦敦、悉尼、莫斯科四个城市游览，要求每个城市有一人游览，每人只游览一个城市，且这6人中甲、乙两人不去巴黎游览，则不同的选择方案共有（ ） A300种B240种C144种D96种,B,（直接法）分三种情况： 情况一,不选甲、乙两个去游览:则有 种选择方案, 情况二:甲、乙中有一人去游览：有 种选择方案; 情况三：甲、乙两人都去游览,有 种选择方案, 综上不同的选择方案共有 + + =240,（间接法）,回目录
12、,1.从4名男生和3名女生中选出4人参加某个座 谈会，若这4人中必须既有男生又有女生，则不同的选法共有_,34,练习题,2. 3成人2小孩乘船游玩,1号船最多乘3人, 2 号船最多乘2人,3号船只能乘1人,他们任选 2只船或3只船,但小孩不能单独乘一只船, 这3人共有多少乘船方法.,27,回目录,特殊元素和特殊位置问题,特殊元素和特殊位置优先策略,例1.由0,1,2,3,4,5可以组成多少个没有重复数字 五位奇数.,解:由于末位和首位有特殊要求,应该优先安 排,以免不合要求的元素占了这两个位置,先排末位共有_,然后排首位共有_,最后排其它位置共有_,位置分析法和元素分析法是解决排列组合问题最常
13、用也是最基本的方法,若以元素分析为主,需先安排特殊元素,再处理其它元素.若以位置分析为主,需先满足特殊位置的要求,再处理其它位置。若有多个约束条件，往往是考虑一个约束条件的同时还要兼顾其它条件,回目录,“特殊元素、特殊位置优先安排法”,对于特殊元素的排列组合问题，一般应先考虑特殊元素，再考虑其它元素。,例2 用0，1，2，3，4这五个数，组成没有重复数字 的三位数，其中偶数共有（ ） A.24 B.30 C.40 D.60,分析：由于该三位数是偶数，所以末尾数字必须是偶数， 又因为0不能排首位，故0就是其中的“特殊”元素，应优先安排。按0排在末尾和不排在末尾分为两类；,0排在末尾时，有 个；
14、0不排在末尾时，先用偶数排个位，再排百位，最后排十位有 个； 由分类计数原理，共有偶数 30 个.,B,解题技巧,回目录,学生要从六门课中选学两门： （1）有两门课时间冲突，不能同时学，有几种选法？ （2）有两门特别的课，至少选学其中的一门，有几种选法？,回目录,（1）有两门课时间冲突,不能同时学，有几种选法？,回目录,解法一：,解法二：,（2）有两门特别的课，至少选学其中的一门，有几种选法？,特殊元素（或位置）优先安排,例 将5列车停在5条不同的轨道上，其中a列车不停在第一轨道上，b列车不停在第二轨道上，那么不同的停放方法有（ ） （A）120种 （B）96种 （C）78种 （D）72种,解
15、：,7种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不种在两端的花盆里，问有多少不同的种法？,练习题,（1）0,1,2,3,4,5这六个数字可组成多少个无重复数字的五位数？,（2）0，1，2，3，4，5可组成多少个无重复数字的五位奇数？,练 习,（3）(2005 北京文)五个工程队承建某项工程的5个不同的子项目，每个工程队承建1项，其中甲工程队不能承建1号子项目，则不同的承建方案共有（ ）种。 （4）(2005 全国II 理)在由数字0，1，2，3，4，5所组成的没有重复数字的四位数中，不能被整除的数共有_个,解：不能被5整除的有两种情况：情况1、首位为5有 种，情况2、首位不是5的
16、有 种，故在由数字 0，1，2，3，4，5所组成的没有重复数字的四位数中， 不能被整除的数共有 + =192(个),192,小结：1、“在”与“不在”可以相互转化。解决某些元素在某些位置上用“定位法”，解决某些元素不在某些位置上一般用“间接法”或转化为“在”的问题求解。,2、排列组合应用题极易出现“重”、“漏”现象，而重”、“漏”错误常发生在该不该分类、有无次序的问题上。为了更好地防“重”堵“漏”，在做题时需认真分析自己做题思路，也可改变解题角度，利用一题多解核对答案,回目录,相邻相间问题,相邻元素捆绑策略,例. 7人站成一排 ,其中甲乙相邻且丙丁相 邻, 共有多少种不同的排法.,解：可先将甲乙两元素
