NOIP中排列组合问题的十种解题策略.doc

《NOIP中排列组合问题的十种解题策略.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、公式法例1：将N个红球和M个黄球排成一行。例如，当N=2，M=3时可得到10种排法。问题：当N=4,M=3时有（）种不同排法？（NOIP2002）解：此题属于不全相异元素的全排列，可以直接代入以下公式（公式中n1+n2+n3+……+nm=N）所以例2：公园门票每张5角，如果有10个人排队购票，每人一张，并且其中一半人恰有5角钱，另一半恰有1元钱，而票房无零钱可找，那么有多少种方法将这10个人排成一列，顺次购票，使得不至于因票房无零钱可找而耽误时间？解：此题属于D[0]>=D[1]排列，可以直接代入以下公式所以二、转换法：深入思考，抓住问题的本质，将原问题转化成排列组合经典问

2、题来解决。例3：某城市的街道是一个很规整的矩形网络（见下图），有7条南北向纵街，5条东西向横街。现在从西南角的A走到东北角的B，最短的走法共有（）种（NOIP2007）BA解：无论怎样走都必须经过6横4纵，因此可把问题转化为4个相同的白球和6个相同的黑球的排列问题。所以三、分类法：按题目条件，把符合条件的排列、组合问题分成互不重复的若干类，分别计算，最后计算总数。例4：小陈现有2个任务A，B要完成，每个任务分别有若干步骤，A=a1→a2→a3，B=b1→b2→b3→b4→b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另

3、一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如……a2→b2→a3→b3……是合法的，而……a2→b3→a3→b2……是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有（）种。（NOIP2009）解：可知B任务中的b1一定做，而且肯定是第一个做的。除了b1外，第一类：只完成A任务，只有1种；第二类：完成A任务和b2，有种；第三类：完成A任务和b2，b3，有种。第四类：完成A任务和b2、b3、b4，有种。第五类：

4、完成A任务和b2，b3，b4，b5，有种。由加法原理可得1+4=10+20+35=70。例5：平面上有三条平行直线，每条直线上分别有7、5、6个点，且不同直线上三个点都不在同一条直线。问用这些点为顶点，能组成（）个不同的三角形？（NOIP2001）解：第一类，7个点中任取2点，5个点中任取1点，有种；第二类，7个点中任取2点，6个点中任取1点，有种；第三类，5个点中任取2点，7个点中任取1点，有种；第四类，5个点中任取2点，6个点中任取1点，有种；第五类，6个点中任取2点，7个点中任取1点，有种；第六类，6个点中任取2点，5个点中任取1点，有种；第七类，7个点中任取1点，5个点

5、中任取1点，6个点任取1点，有种。由加法原理可得，能组成++++++=751个不同的三角形。一、特殊元素（位置）优先法：把有限制条件的元素（位置）称为特殊元素（位置），对于这类问题一般采取特殊元素（位置）优先安排的方法。例6：6个人站成一横排，其中甲不站左端也不站右端，共有多少种不同站法？解法1：（元素分析法）因为甲不能站左右两端，故第一步先让甲排在左右两端之间的任一位置上，有种站法；第二步再让其余的5人站在其他5个位置上，有种站法，由乘法原理可得不同站法共有*=480。解法2：（位置分析法）因为左右两端不站甲，故第一步先让甲以外的5个人任选两人站在左右两端，有种；第二步再让剩

6、余的4个人（含甲）站在中间4个位置，有种，由乘法原理可得不同站法共有=480。一、排除法：对于某些比较复杂的或抽象的问题，可以采用转化思想，从问题的反面去考虑，先求出无限制条件的方法种数，然后去掉不符合条件的方法种数。在应用此法时要注意做到不重不漏。例7:8位同学排成一行，要求某两位同学互不相邻，有多少种排法？解：8位同学排成一行的总数是；把排在一起的两个同学看成一个人的排列总数是，因此排在一起的两个同学的位置可以相互换，所以两位同学排在一起的排列数是2*。所以符合题意的排法为-2*=30240。二、捆绑法：对于要求某几个元素必须排在一起的问题，宜用捆绑法。即将这几个元素看作一

7、个整体，视为一个元素，与其他元素进行排列，然后相邻元素内部再进行排列。例8：书架上有四本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这四本书摆在书架上，满足所有黑皮的书都排在一起的摆法有（）种。（NOIP2008）解：先将C和D“捆绑”在一起看成一个大元素，与A、B全排列有种排法，而C和D又有种排法，由乘法原理可得满足所有黑皮的书都排在一起的摆法有*=12种。例9：由数字1,2,3,4,5,6,7组成无重复数字的七位数，求三个偶数必须相邻的七位数的个数。解：此解可分三步完成