母函数与递推关系省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,Project I,全排列生成算法研究和实现,5,分,选作,C/C+or Java,11,月,20,日前网络学堂提交,目标,Research and Novelty,（,非命题作文，以下内容任选,）,在实现和研究,4,种全排列生成算法基础上进行创新,算法效率和复杂度分析,新算法,任何相关内容创新点,3-6,页,评分标准,Paper (80%),代码以及可执行文件,(20%),选题,分析,完善,1/53,内容回顾,组合生成和组合意义,模型转换,一一对应,定义：对于序列,a,0,a,1,a,2,结构一函数：,G(,x,)=,a,0,+,a,1,x,+,a,2,x,2,+,称函数,G(,x,),是序列,a,0,a,1,a,2,母函数,(,生成函数,generating function),。,(1+,x,),n,是序列,C(,n,0),C(,n,1),C(,n,n,),母函数,g(,x,)=1+,x,+,x,2,+,x,3,+,x,4,+.=1/(1-x),是,f,(,n,)=1,母函数,设级数收敛，,-1,x,1,生成函数,x,没有实际意义,2/53,2,二项式定理,3/53,2.2 递推关系,利用递推关系进行计数这个方法在算法分析中经惯用到,例一.,Hanoi,问题：,N,个圆盘依其半径大小，从下而上套在,A,柱上。每次只允许取一个移到柱,B,或,C,上，而且不允许大盘放在小盘上方。若要求把柱,A,上,n,个盘移到,C,柱上请设计一个方法来，并预计要移动几个盘次。现在只有,A、B、C,三根柱子可用。,设计算法,;,预计它复杂性，即预计工作量,.,4/53,4,2.2 递推关系,算法：,N=2,时,第一步先把最上面一个圆盘套在,B,上,第二步把下面一个圆盘移到,C,上,最终把,B,上圆盘移到,C,上,到此转移完成,A B C,5/53,5,2.2 递推关系,假定,n-1,个盘子转移算法已经确定。,对于普通,n,个圆盘问题,先把上面,n-1,个圆盘经过,C,转移到,B;,第二步把,A,下面一个圆盘移到,C,上,最终再把,B,上,n-1,个圆盘经过,A,转移到,C,上,n=2,时，算法是正确，所以，,n=3,是算法是正确。以这类推。,A B C,6/53,6,2.2 递推关系,令,h,(,n,),表示,n,个圆盘所需要转移盘次。,对于普通,n,个圆盘问题,先把上面,n-1,个圆盘经过,C,转移到,B:,h,(,n,-1),次,第二步把,A,下面一个圆盘移到,C,上,:1,次,最终再把,B,上,n-1,个圆盘经过,A,转移到,C,上：,h,(,n,-1),次,算法复杂度为：,结构母函数为：,求得了母函数，对应序列也就求得,h(n),A B C,7/53,7,2.2 递推关系,所谓形式算法说是假定这些幂级数在作四则运算时，一如有限项代数式一样。,8/53,8,怎样从母函数得到序列？,化为部分分数算法。,由上式可得,：,g(,x,)=1+,x,+,x,2,+,x,3,+,x,4,+.=,即：,9/53,9,2.2 递推关系,或利用递推关系(2-2-1)有,上式左端为：,右端第一项为：,右端第二项为：,10/53,10,2.2 递推关系,例2.,求,n,位十进制数中出现偶数个5数个数,。,先从分析,n,位十进制数出现偶数个5数结构入手 设,p,1,p,2,p,n-1,是,n-1,位十进制数，,若含有偶数个5，则,p,n,取5以外0，1，2，3，4，6，7，8，9九个数中一个，,若,p,1,p,2,p,n-1,只有奇数个5，则,p,n,取5,，使,p,1,p,2,p,n-1,p,n,成为出现偶数个5十进制数,。,解法,1,：,令,a,n,为,n,位十进制数中出现偶数个,5,数个数，,b,n,为,n,位十进制数中出现奇数个5数个数。,设序列,a,n,母函数为,A(x),，序列,b,n,母函数为,B(x),。,11/53,11,a,1,=8,b,1,=1,12/53,12,2.2 递推关系,故得关于母函数,A(x),和,B(x),得连立方程组：,13/53,13,2.2 递推关系,解法二：,n-1,位十进制数全体共,9,10,n-1,个,(,最高位不为,0),，,设所求数为,a,n,设,A(x)=a,1,x+a,2,x,2,+,按照尾数是否为,5,分类：,尾数不是为,5,：,9a,n-1,尾数为,5,，前,n-1,位有奇数个,5,：,14/53,14,2.2 递推关系,验证：,a,1,=8,a,2,=73,15/53,15,1）不出现某特定元素设为,a1,，其组合数为 ，相当于排除,a1,后从,a2,.an,中取,r,个做允许重复组合。,2.2 递推关系,例三：,从,n,个元素,a1,a2,.an,中取,r,个进行允许重复组合。假定允许重复组合数用 表示，其结果可能有以下两种情况。,2）最少出现一个,a1,，取组合数为 相当于从,a1,a2,.an,中取,r-1,个做允许重复组合，然后再加上一个,a1,得从,n,个元素中取,r,个允许重复组合。,16/53,16,2.2 递推关系,因 ，故令,系数,(1-x),不是常数。但,17/53,17,由二项式定理,可得,18/53,18,19/53,母函数,递推关系,递推运算,初始值,代数运算：,化为部分分数算法,20/53,2.3 母函数性质,一个序列和它母函数一一对应。给了序列便得知它母函数；反之，求得母函数序列也随之而定。,为了求满足某种递推关系序列，可把它转换为求对应母函数,G(,x,),，,G(,x,),可能满足一代数方程，或代数方程组，甚至于是微分方程。,最终求逆变换，即从已求得母函数 ,G(,x,),得到序列,a,n,。,关键在于要搭起从序列到母函数，从母函数到序列这两座桥。,21/53,21,2.3 母函数性质,对应母函数分别为,、,不尤其说明,下面假设,、,两个序列,22/53,22,性质,1,：,若,则,例,.,已知,则,例,.,已知,则,m,m,m-1,23/53,23,性质,2,：,则,若,证：,例,.,24/53,24,性质,3,：,证：,若,则,),:,:,:,:,1,2,1,0,2,1,0,2,2,1,0,1,0,0,L,L,L,L,L,L,L,L,L,L,L,L,L,L,L,L,+,+,+,+,+,=,+,+,=,+,=,=,n,n,a,a,a,a,b,n,x,a,a,a,b,x,a,a,b,x,a,b,25/53,25,例,.,已知,类似可得：,若,则,26/53,26,性质,4,则,证,27/53,27,A(,x,)=a,0,+,a,1,x+a,2,x,2,+,A(x)=,a,1,+2a,2,x+3a,3,x,2,+.,例,.,则,性质,5,若,则,性质,6,若,则,求导,积分,28/53,28,性质,7,若,则,证,29/53,29,2.3母函数性质,例.,已知,30/53,30,2.4,Fibonacci,数列,Fibonacci,数列是递推关系又一个经典问题。,Fibonacci,数列是以递归方法來定义：,F,0,=0,，,F,1,=1,，,F,n,=,F,n,-1,+,F,n,-2,（,1,）,斐波那契数列由,0,和,1,開始，之后斐波那契数就由之前两数相加。,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,，,0,不是第一项，而是第,0,项。,31/53,31,1150,年印度数学家研究箱子包裝物件长宽刚好,为,1,和,2,可行方法数目时，首先描述这个数列。,在西方，,1202,年，意大利数学家斐波那契出版了他,算盘全书,。他在书中提出了一个关于兔子繁殖问题：,第一个月有一对刚诞生兔子；,假如一对兔子每个月能生一对小兔（一雄一雌）；,而每对小兔在它出生后第三个月里，又能开始生一对小兔，,兔子永不死去；,由一对出生小兔开始，,50,个月后会有多少对兔子？,第,n,个月相比,n-1,个月多出兔子数是,n-2,个月兔子生出来，即,F,n,=F,n-1,+F,n-2,Leonardo of Pisa,Son of Bonaccio,32/53,32,设,2.4.1递推关系,33/53,2.4.1递推关系,34/53,34,1,）,证实：,2.4.1递推关系,F,n,=F,n-1,+F,n-2,35/53,35,2,）,证实：,2.4.1递推关系,F,n,=F,n-1,+F,n-2,36/53,36,3,）,证实：,2.4.1递推关系,37/53,37,一位魔术师拿着一块边长为8英尺正方形地毯，对他地毯匠朋友说：“请您把这块地毯分成四小块，再把它们缝成一块长13英尺，宽5英尺长方”,魔术,8,8,13,5,0,1,1,2,3,5,8,13,21,.,3,5,F(n)*F(n)F(n-1)F(n+1)=(-1),n,n=0,1,2,38/53,斐波那契螺旋,39/53,39,2.4.4在选优法上应用,设函数 在 点取得极大值。要求用若干次试验找到 点准确到一定程度。最简单方法，把 三等分，令：,以下列图：,40/53,40,2.4.4在选优法上应用,设函数,y,=,f,(,x,),在区间,(,a,b,),上有一单峰极值点，假定为极大点。,所谓单峰极值，即只有一个极值点,，而且当,x,与,偏离越大，偏差,|f(x)-f(,),|,也越大。以下列图：,41/53,41,2.4.4在选优法上应用,依据 大小分别讨论以下：,当 ，则极大点 必在 区间上，区间 能够舍去。,42/53,42,2.4.4在选优法上应用,当 ，则极大点 必在 区间上，区间 能够舍去。,43/53,43,2.4.4在选优法上应用,当 ，则极大点 必在 区间上，区间 和 均能够舍去。,44/53,44,可见做两次试验，最少可把区间缩至原来区间2/3，比如 ，深入在 区间上找极值点。,若继续用三等分法，将面对着这一实事，即其中 点试验没发挥其作用。为此构想在 区间两个对称点 分别做试验。,45/53,45,设保留 区间，继续在 区间下面两个点,x,2,(1-,x,),x,处做试验，若,则前一次 点试验，这一次可继续使用可节约一次试验。由(2-3-6)式有,0.382,，,0.618,0.236,，,0.382,0.146,，,0.236,46/53,46,2.4.4在选优法上应用这就是所谓0.618优选法。即若在 区间上找单峰极大值时，可在,点做试验。比如保留区间 ，因为,，故只要在,点作一次试验。,47/53,47,2.4.4在选优法上应用,优选法中可利用,Fibonacci,数列，和0.618法不一样之点在于它预先确定试验次数，分两种情况介绍其方法。,(,a),全部可能试验数恰好是某个,F,n,。,这时两个试验点放在,F,n-1,和,F,n-2,两个分点上，,假如,F,n-1,分点比很好，则舍去小于,F,n-2,部分；,留下部分共,F,n,-F,n-2,=F,n-1,个分点，其中,第,F,n-2,和第,F,n-3,二试验点，对应原标号是,F,n-2,+F,n-22F,n-2,以及,F,n-3,+F,n-2,=F,n-1,恰好,F,n-1,点是刚才留下来试验能够利用。,假如,F,n-2,点更加好，则舍去大于,F,n-1,部分。,在留下部分共,F,n-1,个分点，下一步,F,n-2,和,F,n-3,二试验点中，恰好,F,n-2,是刚才留下来试验能够利用。,可见在,F,n,个可能试验中，最多用,n-1,次试验便可得到所求极值点。,48/53,48,2.4.4在选优法上应用,(,b),利用,Fibonacci,数列进行优选不一样于 0.618法之点,还在于它适合于参数只能取整数数值情况.如若可能试验数目比 小,但比 大时,能够虚加几个点凑成 个点，但新增加点试验无须真做，可认定比其它点都差点来处理。,49/53,49,2.4.4在选优法上应用,定理：,测试,n,次可将包含单峰极值点区间缩小到原区间 ，其中 是任意小正整数，,证：,对,n,用数学归纳法。,n=2,时，将区间,(a.b),平分成,F(2+1,）,=2,段。在分点（包含端点,a，b）,分别标上,0,，,1,，,2,。在1点两侧取,，在（,1-,）,与,(1+,),两点上测试，不论哪一点较优，保留下来区间长度均为,(1+,),，命题成立。,a,b,0,1,2,1-,1+,50/53,50,2.4.4在选优法上应用,假设对于,n-1，,命题成立,对于,n，,将,(a,b),平分成,F,n+1,段，对分点（包含端点,a，b）,依次标上,0,1,2,。先在,F,n,点与,F,n-1,点测试,不论哪一点较优，保留下来区间均为,F,n,段。,依据归纳假设，再做,n-1,次测试（内含前两次测试之一）可将含极值点区间缩小到,1+,段，即原区间,1/F,n+1,+,。,F,n+1,F,n-1,=F,n,51/53,51,2.4.4在选优法上应用,因,当,n,较大时，可将相继两个测试点取在待测区间0.618及1-0.618处。由,可知，0.618法比 法最多多测试一次。0.618 法优点是无须事先定测试次数。,52/53,52,2.4.4在选优法上应用,定理：设在给定区间内有单峰极值点。假如包含极值点在内可测点为,F,n+2,-1,个，则测试,n,次必可找到极值点，,n2.,证：对,n,用数学归纳法。,n=2,时，,F,n+2,-1=2,，命题成立,假设对于,n-1，,命题成立,下面证实对,n,命题成立。设可测试点标号依次,1,2,F,n,.F,n,+1,F,n+2,-1,。先在,F,n,点及,F,n+1,点测试。不论哪一点较优，保留下来可测点都为,F,n+1,-1,个。,依据归纳假设，再测试,n-1,次必可找到极值点。,而在保留,F,n+1,-1,个可测试点中，有一点（,F,n,点或,F,n+1,点）测试,结果下一次比较时恰好用上，这么总测试次数为,n。,F,n+2,-1 F,n,=F,n+1,-1,53/53,53,