排列--2.ppt

排列 二 问题1从甲 乙 丙3名同学中选出2名参加某天的一项活动 其中1名同学参加上午的活动 1名同学参加下午的活动 有多少种不同的方法 问题2从a b c d这四个字母中 取出3个按照从左到右的顺序排成一列 共有多少种不同的排法 说明 我们将上述两个问题中的同学 字母这两个研究对象抽象为元素 问题1 从3个不同元素 同学 中任意选择2个 按一定顺序 上午 下午 排成一列 求共有多少种不同的排法 问题2 从4个不同元素 字母 中任意选择3个 按一定顺序 左中右 排成一列 求共有多少种不同的排法 问题1 从3个不同元素 同学 中任意选择2个 按一定顺序 上午 下午 排成一列 求共有多少种不同的排法 问题2 从4个不同元素 字母 中任意选择3个 按一定顺序 左中右 排成一列 求共有多少种不同的排法 一般地 从n个不同元素中取出m m n 个元素 按照一定的顺序排成一列 叫做从n个不同元素中取出m个元素的一个排列 排列定义 1 直接计算法 有限制条件问题 某些元素不能在某个 或某些 位置 某个 或某些 位置只能放某些元素 因此进行算法设计时 常优先处理这些特殊要求 特殊元素 位置 优先考虑法 2 间接计算法 先不考虑限制条件 把所有的排列种数算出 再从中减去全部不符合条件的排列数 间接得出符合条件的排列种数 特别注意要不重复 不遗漏 解排列问题常见方法 例1 7位同学站成一排 1 甲 乙两同学必须相邻的排法共有多少种 解 1 先将甲乙进行排列 2 把甲乙当作一个整体 看作一个元素 和其它5个元素 同学 放在一起进行排列 捆绑法 常用在相邻问题中 分两步 根据分步记数原理 排列数为 把须相邻的元素看成一个整体 称为捆绑法 例1 7位同学站成一排 2 甲 乙和丙三个同学都相邻的排法共有多少种 解 1 先将甲乙丙进行排列 2 把甲乙丙当作一个整体 看作一个元素 和其它4个元素 同学 放在一起进行排列 分两步 根据分步记数原理 排列数为 例1 7位同学站成一排 3 甲 乙两同学必须相邻 而且丙不能站在排头和排尾的排法有多少种 解 1 先将甲乙进行排列 2 把甲乙当作一个整体 看作一个元素 和其它5个元素 同学 放在一起进行排列 分两步 根据分步记数原理 排列数为 法一 先安排丙 再安排剩余5个元素 例1 7位同学站成一排 3 甲 乙两同学必须相邻 而且丙不能站在排头和排尾的排法有多少种 解 1 先将甲乙进行排列 2 把甲乙当作一个整体 看作一个元素 和其它5个元素 同学 放在一起进行排列 分两步 根据分步记数原理 排列数为 法二 先从除丙以外的5个元素中选择2个元素放在头和尾 再安排剩余4个元素 例1 7位同学站成一排 4 甲 乙 丙三个同学必须站在一起 另外四个人也必须站在一起 解 1 先将甲乙丙进行排列 3 把甲乙当作一个整体 看作一个元素 将另外4个人当作一个整体 看作一个元素 将两个元素进行排列 分三步 根据分步记数原理 排列数为 2 再将另外4个人进行排列 例2 7位同学站成一排 1 甲 乙两同学不能相邻的排法共有多少种 解 分两步 先将其余五个同学排好 第一步 第二步 再将甲 乙同学分别插入这六个位置 空 此时他们留下六个位置 就称为 空 吧 根据分步记数原理 排列数为 插空法 常用在不相邻问题中 特殊元素后考虑 例2 7位同学站成一排 2 甲 乙和丙三个同学都不能相邻的排法共有多少种 解 分两步 先将其余4个同学排好 第一步 第二步 再将甲 乙 丙同学分别插入这5个位置 空 此时他们留下5个位置 就称为 空 吧 根据分步记数原理 排列数为 例3 5男4女排成一排 按下列要求各有多少种排法 1 男女相间 解 分两步 第一步 先排男生 第二步 再排女生 将4名女生排在4个空位 根据乘法原理 排列数为 例3 5男5女排成一排 按下列要求各有多少种排法 2 女生按指定顺序排列 解 分两步 第一步 先排男生 第二步 再排女生 根据分步记数原理 排列数为 设想有10个位置 先将男生排在其中的任意5个位置上 余下的5个位置排女生 因为女生的位置已经指定 所以她们只有一种排法 相邻元素捆绑法 相离问题插空法 在解决对于某几个元素要求相邻