2015解排列组合问题的常用方法.ppt

处理复杂的排列组合问题时，可以把这个问题退化成一个简单的问题，通过这个简单的问题的解决来找到解题方法，从而进一步解决原来的问题，这种方法叫做“化归策略”。 1.从4名男生和3名女生中选出4人参加某个 座谈会，若这4人中必须既有男生,又有 女生，则不同的选法共有_______ 练习题 3成人2小孩乘船游玩,若1号船最多乘3人, 2号船最多乘2人,3号船只能乘1人,他们 任选2只船或3只船,但小孩不能单独乘 一只船,则这3人共有多少种乘船方法? Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 十四.等价转换、构造模型策略 例14. 马路上有编号为1,2,3,4,5,6,7,8,9的 九只路灯,现要关掉其中的3盏,但不能关 掉相邻的2盏或3盏,也不能关掉两端的2 盏,求满足条件的关灯方法有多少种？ 解：把此问题当作一个排队模型：　在 6盏亮灯的5个空隙中插入3盏熄灯 有________ 种． 一些不易理解的排列组合题，如果能转化为非常熟悉的模型，如占位填空模型，排队模型，装盒模型等，可使问题直观解决！ Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 练习题 某排共有10个座位,若4人就坐,每人左右两边都有空位,那么不同的坐法有多少种? 等价于4人插5空模型: —— —— —— —— —— Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 十五.实际操作穷举策略 例15.设有编号1,2,3,4,5的五个球和编号1,2 　　 3,4,5的五个盒子,现将5个球投入这五 个盒子内,要求每个盒子放一个球，并且 恰好有两个球的编号与盒子的编号相同, 有多少投法？ 解：从5个球中取出2个与盒子对号有___种, 还剩下3球3盒序号不能对应， 利用实际 操作法，如果剩下3,4,5号球, 3,4,5号盒, 3号球装4号盒时，则4,5号球有且只有1种装法： 3号盒 4号盒 5号盒 3 4 5 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 对于条件比较复杂的排列组合问题，不易用公式进行运算，往往利用穷举法或画出树状图会收到意想不到的结果！ 同理3号球装5号盒时，4,5号球有也只有１种装法,由分步计数原理有　　　　　种投法。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 练习题 同一寝室4人,每人写一张贺年卡集中起来, 然后每人各拿一张别人写的贺年卡，则四 张贺年卡不同的分配方式有多少种？ 9 2.给图中区域涂色,要求相邻区 域不同色,现有4种可选颜色,则 不同的着色方法有____种. (2003) 2 1 3 4 5 72 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 十六. 分解与合成策略 例16. 30030能被多少个不同的正偶数整除. 分析：先把30030分解成质因数的乘积形式: 30030=2×3×5 × 7 ×11×13,依题 意可知正偶因数必先取2,再从其余5 　个因数中任取若干个组成乘积，所有 的正偶因数为： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Lt