下载此文档

组合数学算法(一).ppt


文档分类:高等教育 | 页数:约14页 举报非法文档有奖
1/14
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/14 下载此文档
文档列表 文档介绍
一、引言中国是最早研究排列组合的国家。《周易》就被认为是世界上最早讨论排列组合的书,其中的《八卦》和《六十四卦》阵,就属于重复排列问题。我载,幻方是组合数学中构造问题之例,据说“河图”就是一种幻方。历史走着曲折的道路。一些历史悠久的学科,在经历了漫长的不被人们重视的岁月之后,又会重新焕发出青春的活力。组合数学的历史就是如此。它同算术、代数、几何一样古老,源远流长,但却没有它们那种持续不断的发展历程。这不能归咎于它的衰老,而只能解释成历史的青睐尚未到来。历史是公正的,人类创造的每一项伟绩都不至于被遗忘。近几十年来,这门古老的学科年轻了,活跃起来了,开始以前所未有的速度向前发展着,不断取得丰富的成果。促使这种变化出现的最主要动力是二十世纪的计算机科学的迅速发展。计算机科学,数字通讯理论,规划论和试验设计都要求人们把注意力转向研究离散变量的数学学科,其中之一便是组合数学。这种来自尖端学科领域的刺激的出现,激起了这门古老学科领域中从未有过的发展势头,使它一反长期沉睡的状态,成为本世纪最活跃的数学学科之一。铱淑庞台腰辨酌潮侮筷焦盗骂兽电礁报郑闹耕倍殉匠畏卤官文乌肪间姚诈组合数学算法(一)组合数学算法(一)二、排列组合全部组合分析公式的推导基于以下两原理(一)加法原理如果完成一件事情有n种方式A1,∙∙∙,An,每种方式中又有mi种方法(1≤i≤n),且AiAj=Ø,则要完成此事共有一年365天划分为12个月一个国家划分一些省一个班分为几个小组例1离开福州,飞机有60个航班,火车有10个车次,轮船有2个班次,汽车有100个班次。离开福州的方式有60+10+2+100=172呻条昆什粕酮六追采符逆棉悸汛合滁绘普民星磨崩蛇贩讥墒尹酋讥僻杆渊组合数学算法(一)组合数学算法(一)加法原理的例子补充|A|,|B|分别为集合A,B中元素的个数补例1现有长度分别为1,2,∙∙∙,n的细木棍各一根,可以以它们为边构成多少个不同的三角形?解:记三角形三边长度为a,b,c,不妨设a<b<c,则应有a+b>c。以c的长度将这些三角形分类,则可分为c=4,c=5,∙∙∙,c=n这样一些不同的类,分别将各类三角形的集合记作B4,B5,∙∙∙,Bn,则它们构成了所有三角形的集合B的一个分划,则有而在Bk中,三角形三边分别为a<b<k,其中k为定值。于是可将(a,b)对应为平面中的格点,如图。由于还有a+b>k,所以这些点由a=b,a+b=k,b=k三条直线所围成的三角形区域内部。所以当k为偶数时,有当k为奇数时,有所以n为偶数时,n为奇数时,介厢渴蔚汝绿坍稗焚拥逸纯哆核荤阀蝶醉蚁殷簧楔默钒摈于漆糕送陪方阵组合数学算法(一)组合数学算法(一)补例2设[x]表示不超过实数x的最大整数。求方程x2-[x2]=(x-[x])2在区间1≤x≤n中根的个数。解:显然x=n是方程的一个根。下面我们再分别求出方程在区间1≤x<2,2≤x<3,…,n-1≤x<n中的根的个数。为此设这些区间中根的个数为B1,B2,…,Bn-1,即以Bk表示方程在区间k≤x<k+1中根的全体。∵在k≤x<k+1中,有[x]=k,如果再记p=x-[x],就有0≤p<1。于是原来方程就可以写成(k+p)2-[(k+p)2]=p2即k2+2kp=[k2+2kp+p2]注意到[k2+2kp+p2]=k2+[2kp+p2]知上式即为2kp=[2kp+p2]该式右端是一个整数,所以左端也应为整数,即2kp是整数由于k为整数,0≤p<1,所以只有当p=0,1/2k,2/2k,…,(2k-1)/2k时,等式才能成立。从而知原方程在此区间中恰有2k个根,即|Bk|=2k于是由加法原理知原方程在区间1≤x≤n中共有|B1|+|B2|+…+|Bn-1|+1=2+4+…+2(n-1)+1=n2-n+1个根加法原理用途极多,如将其与其他数学原理,例如抽屉原理结合起来,就可以推出许多有趣的数学命题。桥界动厢廷杖癣肖茅烂易氖图放织塔鸣铆鲜绑闯佑戊疫氏躬又啊殷榜制妥组合数学算法(一)组合数学算法(一)(二)乘法原理如果完成一件事情要分几个步骤B1,B2,…,Bn,而每个步骤Bi有mi种方法(1≤i≤n),那么完成这事共有例2某人在进小学、初中、高中时都分别有二所学校可选择,那么他就有多种不同的方式从小学到高中。共8种=2x2x2例3多项式乘积(a1+a2+a3)(b1+b2+b3+b4)(c1+c2+c3+c4+c5+c6)(d1+d2)的展开式中有多少不同的项。解:展式中每项均形如aibjckdl,其中iє{1,2,3},jє{1,2,3,4},kє{1,2,3,4,5,6},lє{1,2}由乘法原理,展式中共有3x4x6x2=144(项)例4在ΔABC的三边上分别取n1,n2,n3个点(不含A,B,C

组合数学算法(一) 来自淘豆网m.daumloan.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数14
  • 收藏数0 收藏
  • 顶次数0
  • 上传人n22x33
  • 文件大小82 KB
  • 时间2020-01-10
最近更新