![常见的一些排列、组合模式和解法_第1页](http://file4.renrendoc.com/view3/M00/0F/0E/wKhkFmYT_VaAJQaWAAMjS-y7TZk037.jpg)
![常见的一些排列、组合模式和解法_第2页](http://file4.renrendoc.com/view3/M00/0F/0E/wKhkFmYT_VaAJQaWAAMjS-y7TZk0372.jpg)
![常见的一些排列、组合模式和解法_第3页](http://file4.renrendoc.com/view3/M00/0F/0E/wKhkFmYT_VaAJQaWAAMjS-y7TZk0373.jpg)
![常见的一些排列、组合模式和解法_第4页](http://file4.renrendoc.com/view3/M00/0F/0E/wKhkFmYT_VaAJQaWAAMjS-y7TZk0374.jpg)
![常见的一些排列、组合模式和解法_第5页](http://file4.renrendoc.com/view3/M00/0F/0E/wKhkFmYT_VaAJQaWAAMjS-y7TZk0375.jpg)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
#1111P*P*P*P6982排列按照元素的排列方式又可分为三种排列⑴线排列;⑵圆排列;⑶重排列。一、线排列:先考察一个简单的问题,有红、蓝、白三只球,要放到编号为1,2,„,10的十个盒子中,如果每个盒子只能装一只球,问把球放到盒子中的不同放法的种类。分析:每次放一只球,不妨依此顺序:放红球T放蓝球T放白球。放红球的方法有10种(红球可放在10个盒子的任一个中)放蓝球的方法有9种(红球可放在9个盒子的任一个中)放白球的方法有8种(红球可放在8个盒子的任一个中)根据乘法原理:这些球的不同放法总共有10X9X8=720(种)根据上例,不难推广到一般,得到线排列的定义:从n个不同的元素中,取r个按次序排列,称为从n中取r个排列,记为P(n,r)。显然,P(n,r)=n(n-1)(n-2)・・・(n-r+1)=n!/(n-r)!其中,当r=0时,一个元素也不取,算作是取0个元素的一种排列,即P(n,0)=1;当r=n时,有P(n,n)=n!,即n的全排列;而把0<r<n的情况称为选排列。[例]在五天之内安排三次考试,且不允许一天内有两次考试,那末一共有多少种安排法?解:不妨把三次考试看作是三只颜色不同的球,五天看作是五个编号不同的盒子,P(5,3)=5x4x3=60[思考]确定各位数中不重复的四位十进制数的个数。、圆排列:从集合S={a「a2,a3,…,a}的n个不同元素中,取出r个元素按照某种次序(如逆时针)排成一个圆圈,称这样的排列为圆排列。气週屯…牛,週屯…牛%a3a4^ana1a25毎气週…%-!需要注意的是,一个圆排列旋转可得另一个圆排列,这两个圆排列是相同的,例如取出r个元素气週屯…牛,週屯…牛%a3a4^ana1a25毎气週…%-!这r个线排列在圆排列中只能算一个。一个圆排列可以产生r个线排列,而总共有P(n,r)个线排列,因此圆排列的个数为:P(n,r)/r=n!/(r(n-1)!)[例]有8人围圆桌就餐,问有多少种就座方式?如果有两人不愿坐在一起,又有多P(8,8)8P(8,8)8二7!(种)少种就座方式?解:n=8,r=8,因此8人围圆桌就餐的就座方式有:设不愿坐在一起的两人为甲和乙。不妨考虑甲乙坐在一起时的情况。此时,相当于7人围桌而坐,其就坐方式为7!/7(n=7,r=7)。而甲乙坐在一起又有两种情况,这样,甲和乙坐在一起时共有2X6!种就坐方式。因此,甲和乙不坐在一起的就座方式共有:7!-2X6!=3600(种)三、重排列:前面讨论的是从n个互不相同的元素组成的集合S={a「a2,…,aj中选r个元素进行排列、在每种排列中每个元素至多只出现一次的情况。现在考虑允许重复出现的情况,即考虑在重集S={中],k2・a2,…,/aj中选r个元素进行排列。根据重复数k1,k2,„,kn是否趋向I重排列又可分为无限重排列和有限重排列。1.无限重排列:考查把三个不同颜色的球放在十个不同的盒子中问题。若每个盒子能容纳的球的只数无限,那么,蓝球和白球也能像红球一样放入十个盒子中的任一个,所以放置的方法总数是:10X10X10=103=1000(种)一般地,从n个不同元素中取r个按次序排列,若每个元素无限次重复(即k1=k2=„=k=-),则称排列为无限次排列,其排列数等于nr。"[例]无线电收发报机有‘•’和‘一’(短、长)两种信号,用四个信号代表一个阿拉伯数码,问可以表示多少个不同码?解:对无线电收发报机来说,有两种信号,取四个表示一个数码,这是一种重排列:四个信号:□□□□每个信号两种表示:•—………因此,总共可以表示不同的数码个数是:24=16(个)这样,对于十进制记数法中只有十个不同的数码是完全够用了。同理,通用明码用四个数码表示一个汉字,可以表示出的汉字个数为104=10000。若不允许重复,四个十进制码仅能表示P(10,4)=5040个汉字,显然是不够的。2.有限重排列:若允许元素有限次重复,那S={匕牛,k2・a2,…,叫叫}(ki#^),则从所有元素中取r个有次序排列的种数又如何计算呢?[例]有两只红球、一只蓝球和一只白球放到编号不同的十个盒子中去的方法总数是多少?解:将两只红球分别涂成深红色和浅红色,使之能区别,于是问题转化为四只不同颜色的球放到十个盒子中去的方法种数是:P(io,4)=5040。在这5040种方法中,若不区分红球的深浅,那么两种方法变成一种方法,因此,两只红球、一只蓝球和一只白球放入十个编号不同的盒子的方法种数有:5040/2=2520。一般地,把r只彩色球放到n个编号不同的盒子中去的方法种数是:P(n,r)r!r!...r!i2t其中,ri表示第i种彩球有ri只,i=1,2,3,…,t,且有r=r1+r2Hrt。当r=n时,有:n!n!...n!12t其中,n1表示n1个相同元素,…,叫表示nt个相同元素且有片+出叫=n。[思考]某市区中的一处棋盘形街道,有南北方向街道(纵街)5条,东西方向街道(横街)8条,见下图,某人从东南角走到西北角,要按最短路径走(就是只能向西或向北走),共有几种走法?南
附:第三届全国青少年信息学(计算机)奥林匹克分区联赛复赛试题(初中组竞赛用时:3小时)―、设有一个N*M方格的棋盘(1WNW100,1WMW100)。(30%)求出该棋盘中包含有多少个正方形、多少个长方形(不包括正方形)例如:当N=2,M=3时:正方形的个数有8个,即边长为1的正方形有6个;边长为2的正方形有2个。a
bc
de
其中:a〜i分别表示1,2,…,9中的一个数字,并要求满足下列条件:⑴a<f<i;⑵b<d,g<h,c<e;⑶a+b+d+f=f+g+h+i=i+e+c+a=P程序要求:根据输入的边长P,输出所有满足上述条件的三角形的个数及其中的一种方案。三、设有一个N*M(1WNW50,1WMW50)的街道(如下图):(40%)北东南B(9,5)A(1,北东南B(9,5)A(1,1)规定行人从A出发,在街道上只能向东或向北方向行走。如下为N=3,M=3的街道图,从A出发到达B共有6条可供走的路径:B(N,M)A5A2A—A1—A2—A5—B(N,M)A5A2A—A1—A4—A5—BA—A1—A4—A7—BA—A3—A4—A5—BA—A3—A4—A7—BA—A3—A6—A7—B若在N*M的街道中,设置一个矩形障碍区域(包括围住该区域的街道)不让行人通过,如上图中用“*”表示的部分。此矩形障碍区域用2对顶点坐标给出,图中的2对顶点
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2023年测定仪安全仪器资金筹措计划书
- 2024车辆维修投标文件-合同协议-表格模板-应用文书
- 家政服务人员聘用协议
- 集体合同与个人劳动合同的区别
- 2023年乙丙醇胺资金申请报告
- 车库使用权收回协议书
- 拆迁户离婚协议书
- 超市2个人合伙人协议书
- 拆屋安全协议书
- 苏教译林版小学英语单词完全掌握
- 牛津译林版 时态专项练习选择题50题(含答案)
- 教案-第二章 企业制造战略
- 道路交通事故处理课件
- 2023年opencv教程讲解模板
- 第8章婴幼儿营养常识
- 英语速记小学800单词课件
- 药品不良反应 药品不良反应监测和报告 药品不良反应
- 儿童感觉统合能力发展评定量表(含原始分与标准分转换表)988
- 心肺复苏后的高级生命支持
- 加强教师法制教育-提升教师法治意识
- 做最好的中层
评论
0/150
提交评论