《应用举例.ppt》由会员分享，可在线阅读，更多相关《应用举例.ppt（27页珍藏版）》请在三一文库上搜索。
1、例1 9个数字(1到9)和4个四则运算符(+,-,)组成的13个元素，求由其中的n个元素的排列构成一算术表达式的个数。,这里所说的算术表达式指的是普通意义下的四则运算表达式，不允许运算符连续出现，最后一位必定是数字。,假设n个元素的算术表达式个数为an。由于最后一位必定是数字，接下来看第n-1位，即倒数第二位。,2.5 应用举例,若第n-1位是数字，则前n-1位构成算术表达式，个数为an-1，加上最后一位有9种取法，因此这样的n位算术表达式个数为9an-1。,娠姻绳经靳钉映男簇僳想迄考远猜树嘱沤闪狡挂婉惯烈作匠黎吗击穆超昌应用举例应用举例,若第n-1位是运算符，则第n-2位必定是数字(不允许两
2、个运算符连续出现)，即前n-2位构成算术表达式，个数为an-2，加上最后一位有9种取法，倒数第二位有4种取法，这样的n位算术表达式个数为36an-2。,因此可以得到递推关系式：,初始条件为a1=9，a2=90。,这里a2=90指的是81个两位数和-1到-9。,为了后面的计算方便，我们把a1，a2代入原递推关系反解出a0=1/4。,从特征方程x2-9x-36=0解出特征根为12，-3。,早润刃星婪叭肪紊锤衣搓肪虱石扎兼哉戊磷拷阮朴挠谈炬爵找乾墙竿艳锰应用举例应用举例,因此可以设,代入初始条件有,因此有：,由此解出,欢滁纱诣夯竞便体夷躬八貌零变妖棘妈啤撬与簇债坎献鸽勉欲诸王涅矾院应用举例应用举例,
3、例2 n条直线把平面分成多少个区域？假定直线两两相交且无三线共点。,设n条直线把平面分成Dn个区域。,这是一个非齐次递推关系。由于1是1重特征根，因此特解应设为2次多项式，加上齐次方程的通解为常数，因此可以设,代入初始条件：D1=2，D2=4，D3=7，解得A=B=1/2,C=1。因此有,第n条直线被其它n-1条直线分成n段，这n段刚好对应增加了n个新的区域。因此有,指谢点登蒙着穆泄运磨觅瓜乡亨争鳃枢樊啃料扫杆终寄澈板审下熬门镣谜应用举例应用举例,例3 设有n条封闭的曲线，两两相交于两点，任意三条封闭曲线不相交于一点。求这样的 n条曲线把平面分割成几个部分？,设n条曲线把平面分割成an个部分。
4、,这2n-2个交点把第n条曲线分成2n-2段。,这是一个线性常系数非齐次递推关系。,第n条曲线与其他n-1条曲线共有2(n-1)个交点。,这2n-2段刚好是增加的区域的边界，即增加了2n-2个区域。因此有,啸惋哆忧啊狼筷哦刘沁怎茧宇掸哎舶沁慎形干口誊旅侄虾钟宇慎旺章彭利应用举例应用举例,右端项为一次多项式，但因为1是1重特征根，因此特解应该设为二次多项式。加上齐次递推关系的通解为常数，因此有,对于初始条件，显然有a1=2，a2=4。,在递推关系an-an-1=2n-2中令n=1还可以得到a0=2。,把这三个初始条件代入有,因此有：,姜锻心汾绦凡胺醛水坎兢枯桌千顾伊吉擒驮兴崩恫迪糊抠狮吓探绦滤溪
5、扛应用举例应用举例,例4 空间有n个平面，任意三个平面交于一点，且无四平面共点。这样的n个平面把空间分成多少个不重叠的区域？,设这样的n个平面把空间分成an个区域。,因此关键在于第n个平面被其它n-1个平面分成多少个区域？,题目的条件保证了第n个平面与其它n-1个平面各有一条交线，而且这些直线两两相交，且无三线共点。,第n个平面被其它n-1个平面分成一些区域，这些区域刚好对应到新增加了的空间区域个数。,因此根据例2的结论，这n-1条直线把第n个平面分成的区域个数为：Dn-1=n(n-1)/2+1。,蘸能泣紫艺突管汐狼习热信州巩觉曼僵雀报唐晤澳暇御莫采铱倚颅述宛尔应用举例应用举例,这表明,与前面
6、的讨论类似，这个递推关系的解应该是三次多项式，即可设,初始条件有a1=2，a2=4，a3=8，a0=1。代入有,因此有,燎距丙历慷番等饭盼倾潮仿走投烤缨粥软橱烯鹏而汪摆汛振丝斯耿死覆屁应用举例应用举例,例5 平面上有一点P，它是n个区域D1,D2,Dn的共同交界点。现取k种颜色对这n个区域进行着色，要求相邻两个区域着的颜色不同。求着色的方案数。,设不同的着色方案数为an。,(1) D1和Dn-1着色相同；,满足条件的着色方案分为两类：,(2) D1和Dn-1着色不同；,(1) 从D1到Dn-2的着色方案数为an-2(D1和Dn-2看作相邻，着色不同)。,然后Dn-1和D1同色，Dn有k-1种颜
7、色可选。,这种情形的总方案数为(k-1)an-2。,宠债霸晨棠篱咳禽位珊眩础公硝离术师唬剧喳板涛渊搐牛端隔掸戍增尾憎应用举例应用举例,特征方程为：x2-(k-2)x-(k-1)=0。,由初始条件a2=k(k-1)，a3=k(k-1)(k-2)，有,(2) 从D1到Dn-1的着色方案数为an-1(D1和Dn-1看作相邻，着色不同)。,然后Dn有k-2种颜色可选。这种方案数为(k-2)an-1。,因此可以得到递推关系式：,特征根为：k-1，-1。因此有,萄戳抵弧具韩价朝版九纱岁盏救选割徐闻卒欲彤痴散韦溢裕杏盒芽励蛤堵应用举例应用举例,有,由此解得：,把a0=k，a1=0代入,因此满足条件的不同着色
8、方案数为：,律幌意斗亚上惮钓驴譬潮盎殴七禁误揍炒坦矾青啡娱夸沸皿沪夯立肿缎芋应用举例应用举例,例6 求n位二进制数中最后三位出现010图象的数的个数。,这里所说的010图象是指：对于n位2进制数从左向右进行扫描，一旦出现010图象，便从这图象后面一位继续开始扫描。,例如对11位2进制数00101001010从左向右的扫描结 果应该是2-4，7-9位出现010图象，即,而不是4-6，9-11位出现的010图象，即不是,注意最后三位是010和最后三位出现010图象的区别。,疏钠冰凡登娜白胯语灭皿区马镶假皑辖苇糊朔技汪起火沙司哎块蹲盏缎佑应用举例应用举例,最后三位是010的n位二进制数显然有2n-3
9、个。,设最后三位出现010图象的数的个数为an。,这些数可以分为两类：最后三位出现010图象以及第n-4位至第n-2位出现010图象。,这是一个二阶线性常系数非齐次递推关系。初始条件为a3=1，a4=2。,最后三位出现010图象的数有an个，第n-4位至第n-2位出现010图象的数的个数为an-2。因此有,代入递推关系解得： a2=2-a4=0，a1=1-a3=0，a0=1/2-a2=1/2。,辗绣第历水航粪家仰绘逞婚变夫硼宰歌朔品潮摇宴趴艇汕嫩倪疑证倘涝鲤应用举例应用举例,先求对应的齐次递推关系的通解。,特征方程为x2+1=0，特征根为i和-i。,由于右端项是2n-3，因此可以设一个特解为C
10、2n。,所以递推关系的解可以表示为：,因此齐次递推关系的通解为：,贯橙专字勋舀室糕撰腑郊灿痈盒呸尉叁鸟咕痴刘锨详紊小两胶您烧佩型脖应用举例应用举例,代入初始条件有：,由此解得：,因此最后三位出现010图象的数的个数为：,菊绵懊逻鞭淌棉瞳蔑擞杆拙谜灌狭晰眼狈缉浪抨哼痞慢猩裹弦嘱飘诽惦逾应用举例应用举例,例7 求n位二进制数中最后三位第一次出现010图象的数的个数。,设最后三位第一次出现010图象的数的个数为an。,同上例，最后三位是010的数有2n-3个。,这些数包括：,(1) 最后三位第一次出现010图象的，个数为an：,(2) 第n-4至n-2位第一次出现010图象的，个数为an-2：,郎摄
11、懈闽蹈懦碘沮砒勃葬插札轴蓖察莱矛缸迸屉烽某赏缚硕陵射旷巷混疫应用举例应用举例,(3) 第n-5至n-3位第一次出现010图象的，个数为an-3：,(4) 第n-6至n-4位第一次出现010图象的：,注意到第n-3位可以取1或0，因此这种数有2an-4个。,一般的，对于k3，第n-k-2至第n-k位第一次出现010图象的数的个数为2k-3an-k，因为从第n-k+1至第n-3的这k-3位每位都可取1或0。,因此有：,锋销父利脏揩幕搞鞠娩巷聚歧徒铣歹昭情泪胡凿借恳釜拴码籍依景刻茅枫应用举例应用举例,初始条件为a3=1，a4=2，a5=3。,注意a5=3是因为最后3位是010的5位数有4个：,000
12、10，01010，10010，11010.,但其中01010不满足条件。,这不是一个常系数递推关系，左边的递推关系中的项数和系数都是在不断变化的。,例如，令n=6，则a6+a4+a3=8，由此得到a6=5。,例如，令n=7，则a7+a5+a4+2a3=16，由此得到a7=9。,得到一般通项表达式的方法比较特别。,切服怂秽挂熄馁工呸舍探顷晒糠魂嘛炮肤降蓝响脐娟虚章震孪赘云饺播克应用举例应用举例,设序列an对应的母函数为：,则有：,x3:,x4:,x5:,+),阐捧懒司蛊喻坞硫鳞践亿兢洒柱誉剁廓膛锅矩授颧颧默治浊褪撬切合挎练应用举例应用举例,整理得：,因此有：,巩霓长妊轰焊敖涝里啄版包墓湘蜀各赌淹
13、乞兵姨叮仿两充吃韦肝狄淀刽仪应用举例应用举例,例8 计算如下电路中各点的电压vj(j=1,2,n)：,取如右图所示部分电路：,根据欧姆定律有,此外还有：ij+1=ij+vj+1/2。,牧曹满仔悉耪屈袭邢束芜董读饯潭它孺娘豁循驼五倪影汀扮锅蜀辐毛声姓应用举例应用举例,消去ij即得到关于vj的递推关系式：,或,特别的，由(v1-v0)/4=v0/2，可得v1=3v0。,这是一个线性常系数齐次递推关系。,特征方程为：x2-4x+1=0，特征根为： 因此设,代入初始条件：,菊震蔓隐室反陨上掳间根袜侈闪戒碾统岿胎碎怠炽褪砧积侍瑟角泻雾佳戍应用举例应用举例,解得：,则有,若电源电压v已知，则可以由,解出v
14、0，从而得到所有的vj。,扒落测锨掠堑窑州挑甭菠弟尹词惑鳞疆司椎藤父转默烹极瓷陆引侯药抢簇应用举例应用举例,例9 计算如下电路的等效电阻(总电阻)：,Rn可以看成是Rn-1和其他三个电阻串并联所得，即：,因此有：,雏毅杰饰匪俄饱村揽当息单汇帛口膀登罢猴玲论耿鼎盏态使根楔蓄淋切粗应用举例应用举例,这是一个非线性递推关系。初始条件为R1=R。,令Rn=an/bn，a1=R，b1=1。,则有,因此可以令,消去an有,粱溯闭秘邮摊维拥物粮骤什区褪漓殆泥球窘矾骚鹃篙坚沾益拆冗刃豹肖法应用举例应用举例,这是一个线性常系数齐次递推关系。,特征方程为x2-4Rx+R2=0，特征根为,因此可以设,代入初始条件有,因此有,疥嫂牛彝杉润旷助去牟彰舆谗厚憨节咏潦岸饿酒抽规讳农瞄毗蝶狱壁牺刚应用举例应用举例,然后有,因此有,筑专卵漳淤延韩揽梢及钦臭锻疲赣德酚蟹统海但喻顿岁沏锥衰智垣札嘱堵应用举例应用举例,