1、Project I全排列生成算法研究和实现5分选作C/C+or Java11月20日前网络学堂提交目标Research and Novelty（非命题作文，以下内容任选）在实现和研究4种全排列生成算法基础上进行创新算法效率和复杂度分析新算法任何相关内容创新点3-6页评分标准Paper (80%)代码以及可执行文件(20%)选题分析完善1/53内容回顾组合生成和组合意义模型转换一一对应定义：对于序列定义：对于序列a0,a1,a2,结构一函数：结构一函数：G(x)=a0+a1x+a2x2+,称函数称函数G(x)是序列是序列a0,a1,a2,母函数母函数(生成函数生成函数 generating fu
2、nction)。(1+x)n是序列是序列C(n,0),C(n,1),C(n,n)母函数母函数g(x)=1+x+x2+x3+x4+.=1/(1-x)是是f(n)=1母函数母函数设级数收敛，设级数收敛，-1x1生成函数生成函数x没有实际意义没有实际意义2/532二项式定理3/532.2 2.2 递推关系递推关系 利用递推关系进行计数这个方法在算法分析中经惯用到 例一.Hanoi问题：N个圆盘依其半径大小，从下而上套在A柱上。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上n个盘移到C柱上请设计一个方法来，并预计要移动几个盘次。现在只有A、B、C三根柱子可用。设计算法;预计
3、它复杂性，即预计工作量.4/5342.2 2.2 递推关系递推关系算法：算法：N=2时第一步先把最上面一个圆盘套在B上第二步把下面一个圆盘移到C上 最终把B上圆盘移到C上 到此转移完成A B C5/5352.2 2.2 递推关系递推关系 假定n-1个盘子转移算法已经确定。对于普通n个圆盘问题,先把上面n-1个圆盘经过C转移到B;第二步把A下面一个圆盘移到C上最终再把B上n-1个圆盘经过A转移到C上n=2时，算法是正确，所以，n=3是算法是正确。以这类推。A B C6/5362.2 2.2 递推关系递推关系令h(n)表示n个圆盘所需要转移盘次。对于普通n个圆盘问题,先把上面n-1个圆盘经过C转移
4、到B:h(n-1)次第二步把A下面一个圆盘移到C上:1次最终再把B上n-1个圆盘经过A转移到C上：h(n-1)次算法复杂度为：结构母函数为：求得了母函数，对应序列也就求得h(n)A B C7/5372.2 2.2 递推关系递推关系所谓形式算法说是假定这些幂级数在作四则运算时，一如有限项代数式一样。8/538怎样从母函数得到序列？化为部分分数算法。由上式可得：g(x)=1+x+x2+x3+x4+.=即：9/5392.2 2.2 递推关系递推关系 或利用递推关系(2-2-1)有 上式左端为：右端第一项为：右端第二项为：10/53102.2 2.2 递推关系递推关系例例2.2.求n位十进制数中出现偶
5、数个5数个数。先从分析n位十进制数出现偶数个5数结构入手 设p1p2pn-1是n-1位十进制数，若含有偶数个5，则pn取5以外0，1，2，3，4，6，7，8，9九个数中一个，若p1p2pn-1 只有奇数个5，则pn取5，使p1p2pn-1pn 成为出现偶数个5十进制数。解法1：令an为n位十进制数中出现偶数个5数个数，bn为n位十进制数中出现奇数个5数个数。设序列an母函数为A(x)，序列bn母函数为B(x)。11/5311a1=8,b1=112/53122.2 2.2 递推关系递推关系故得关于母函数A(x)和B(x)得连立方程组：13/53132.2 2.2 递推关系递推关系解法二：解法二：
6、n-1位十进制数全体共910n-1个(最高位不为0)，设所求数为an,设A(x)=a1x+a2x2+,按照尾数是否为5分类：尾数不是为5：9an-1尾数为5，前n-1位有奇数个5：14/53142.2 2.2 递推关系递推关系验证：a1=8,a2=7315/5315 1）不出现某特定元素设为a1，其组合数为 ，相当于排除a1后从a2,.an 中取r个做允许重复组合。2.2 2.2 递推关系递推关系例三：例三：从n个元素a1,a2,.an中取r个进行允许重复组合。假定允许重复组合数用 表示，其结果可能有以下两种情况。2）最少出现一个a1，取组合数为 相当于从a1,a2,.an中取r-1个做允许重
7、复组合，然后再加上一个a1得从n个元素中取r个允许重复组合。16/53162.2 2.2 递推关系递推关系 因 ，故令系数(1-x)不是常数。但17/5317 由二项式定理 可得18/531819/53母函数递推关系递推运算初始值代数运算：化为部分分数算法20/532.3 2.3 母函数性质母函数性质 一个序列和它母函数一一对应。给了序列便得一个序列和它母函数一一对应。给了序列便得知它母函数；反之，求得母函数序列也随之而知它母函数；反之，求得母函数序列也随之而定。定。为了求满足某种递推关系序列，可把它转换为为了求满足某种递推关系序列，可把它转换为求对应母函数求对应母函数G(x)，G(x)可能满
8、足一代数方程，可能满足一代数方程，或代数方程组，甚至于是微分方程。或代数方程组，甚至于是微分方程。最终求逆变换，即从已求得母函数最终求逆变换，即从已求得母函数 G(x)得到序列得到序列 an。关键在于要搭起从序列到母函数，从母函数到序列这两座桥。关键在于要搭起从序列到母函数，从母函数到序列这两座桥。21/53212.3 2.3 母函数性质母函数性质对应母函数分别为对应母函数分别为、不尤其说明不尤其说明,下面假设下面假设、两个序列两个序列22/5322性质性质1：若则 例例.已知则 例例.已知则mmm-123/5323 性质性质2：则若证：证：例例.24/5324 性质性质3：证：证：若则 ):
9、1 2102102210100LLLLLLLLLLLLLLLL+=+=+=nnaaaabnxaaabxaabxab25/5325 例例.已知已知 类似可得：类似可得：若则26/5326性质性质4则证27/5327 A(x)=a0+a1x+a2x2+,A(x)=a1+2a2x+3a3x2+.例例.则性质性质5 5 若若则则性质性质6 6若若则则求导积分28/5328性质性质7 7 若若则则证证29/53292.32.3母函数性质母函数性质 例例.已知 30/53302.4 2.4 FibonacciFibonacci数列数列 Fibonacci数列是递推关系又一个经典问题。数列是递推关系又一个经
10、典问题。Fibonacci数列是以递归方法來定义：数列是以递归方法來定义：F0=0，F1=1，Fn=Fn-1+Fn-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/53311150年印度数学家研究箱子包裝物件长宽刚好年印度数学家研究箱子包裝物件长宽刚好 为为1和和2可行方法数目时，首先描述这个数列。可行方法数目时，首先描
11、述这个数列。在西方，在西方，1202年，意大利数学家斐波那契出版了他年，意大利数学家斐波那契出版了他算盘算盘全书全书。他在书中提出了一个关于兔子繁殖问题：。他在书中提出了一个关于兔子繁殖问题：第一个月有一对刚诞生兔子；第一个月有一对刚诞生兔子；假如一对兔子每个月能生一对小兔（一雄一雌）；假如一对兔子每个月能生一对小兔（一雄一雌）；而每对小兔在它出生后第三个月里，又能开始生一对而每对小兔在它出生后第三个月里，又能开始生一对小兔，小兔，兔子永不死去；兔子永不死去；由一对出生小兔开始，由一对出生小兔开始，50个月后会有多少对兔子？个月后会有多少对兔子？第第n个月相比个月相比n-1个月多出兔子数是个月
12、多出兔子数是n-2个月兔子生出来，个月兔子生出来，即即Fn=Fn-1+Fn-2 Leonardo of PisaSon of Bonaccio 32/5332 设2.4.12.4.1 递推关系递推关系33/532.4.12.4.1 递推关系递推关系34/5334 1）证实：证实：2.4.12.4.1 递推关系递推关系Fn=Fn-1+Fn-235/5335 2）证实：证实：2.4.12.4.1 递推关系递推关系Fn=Fn-1+Fn-236/5336 3）证实：证实：2.4.12.4.1 递推关系递推关系37/5337一位魔术师拿着一块边长为8英尺正方形地毯，对他地毯匠朋友说：“请您把这块地毯分成
13、四小块，再把它们缝成一块长13英尺，宽5英尺长方”魔术881350,1,1,2,3,5,8,13,21,.35F(n)*F(n)F(n-1)F(n+1)=(-1)nn=0,1,238/53斐波那契螺旋斐波那契螺旋 39/53392.4.42.4.4在选优法上应用在选优法上应用 设函数 在 点取得极大值。要求用若干次试验找到 点准确到一定程度。最简单方法，把 三等分，令：以下列图：40/53402.4.42.4.4在选优法上应用在选优法上应用 设函数y=f(x)在区间(a,b)上有一单峰极值点，假定为极大点。所谓单峰极值，即只有一个极值点，而且当x与偏离越大，偏差|f(x)-f()|也越大。以下
14、列图：41/53412.4.42.4.4在选优法上应用在选优法上应用 依据 大小分别讨论以下：当 ，则极大点 必在 区间上，区间 能够舍去。42/53422.4.42.4.4在选优法上应用在选优法上应用 当 ，则极大点 必在 区间上，区间 能够舍去。43/53432.4.42.4.4在选优法上应用在选优法上应用 当 ，则极大点 必在 区间上，区间 和 均能够舍去。44/5344 可见做两次试验，最少可把区间缩至原来区间2/3，比如 ，深入在 区间上找极值点。若继续用三等分法，将面对着这一实事，即其中 点试验没发挥其作用。为此构想在 区间两个对称点 分别做试验。45/5345 设保留 区间，继续
15、在 区间下面两个点x2,(1-x)x 处做试验，若则前一次 点试验，这一次可继续使用可节约一次试验。由(2-3-6)式有0.382，0.6180.236，0.3820.146，0.23646/53462.4.42.4.4在选优法上应用在选优法上应用 这就是所谓0.618优选法。即若在 区间上找单峰极大值时，可在 点做试验。比如保留区间 ，因为 ，故只要在 点作一次试验。47/53472.4.42.4.4在选优法上应用在选优法上应用 优选法中可利用Fibonacci数列，和0.618法不一样之点在于它预先确定试验次数，分两种情况介绍其方法。(a)全部可能试验数恰好是某个Fn。l这时两个试验点放在
16、Fn-1和Fn-2两个分点上，l假如Fn-1分点比很好，则舍去小于Fn-2部分；l留下部分共Fn-Fn-2=Fn-1个分点，其中第Fn-2和第Fn-3二试验点，对应原标号是Fn-2+Fn-2=2Fn-2以及Fn-3+Fn-2=Fn-1,恰好Fn-1点是刚才留下来试验能够利用。l假如Fn-2点更加好，则舍去大于Fn-1部分。l在留下部分共Fn-1个分点，下一步Fn-2和Fn-3二试验点中，恰好Fn-2是刚才留下来试验能够利用。可见在Fn个可能试验中，最多用n-1次试验便可得到所求极值点。48/53482.4.42.4.4在选优法上应用在选优法上应用 (b)利用Fibonacci数列进行优选不一样
17、于 0.618法之点,还在于它适合于参数只能取整数数值情况.如若可能试验数目比 小,但比 大时,能够虚加几个点凑成 个点，但新增加点试验无须真做，可认定比其它点都差点来处理。49/53492.4.42.4.4在选优法上应用在选优法上应用 定理：定理：测试n次可将包含单峰极值点区间缩小到原区间 ，其中 是任意小正整数，证：证：对n用数学归纳法。n=2时，将区间(a.b)平分成F(2+1）=2 段。在分点（包含端点a，b）分别标上0，1，2。在1点两侧取，在（1-）与(1+)两点上测试，不论哪一点较优，保留下来区间长度均为(1+)，命题成立。ab0121-1+50/53502.4.42.4.4在选
18、优法上应用在选优法上应用 假设对于n-1，命题成立 对于n，将(a,b)平分成Fn+1段，对分点（包含端点a，b）依次标上0,1,2。先在Fn点与Fn-1点测试不论哪一点较优，保留下来区间均为Fn段。依据归纳假设，再做n-1次测试（内含前两次测试之一）可将含极值点区间缩小到1+段，即原区间1/Fn+1+。Fn+1 Fn-1=Fn51/53512.4.42.4.4在选优法上应用在选优法上应用 因 ,当n较大时，可将相继两个测试点取在待测区间0.618及1-0.618处。由 可知，0.618法比 法最多多测试一次。0.618 法优点是无须事先定测试次数。52/53522.4.42.4.4在选优法上
19、应用在选优法上应用 定理：设在给定区间内有单峰极值点。假如包含极值点在内可测定理：设在给定区间内有单峰极值点。假如包含极值点在内可测点为点为Fn+2-1个，则测试个，则测试n次必可找到极值点，次必可找到极值点，n2.证：对证：对n用数学归纳法。用数学归纳法。n=2时，时，Fn+2-1=2 ，命题成立，命题成立 假设对于假设对于n-1，命题成立命题成立 下面证实对下面证实对n命题成立。设可测试点标号依次命题成立。设可测试点标号依次1,2,Fn,.Fn+1,Fn+2-1。先。先在在Fn点及点及Fn+1点测试。不论哪一点较优，保留下来可测点都为点测试。不论哪一点较优，保留下来可测点都为Fn+1-1个。个。依据归纳假设，再测试依据归纳假设，再测试n-1次必可找到极值点。次必可找到极值点。而在保留而在保留Fn+1-1个可测试点中，有一点（个可测试点中，有一点（Fn点或点或Fn+1点）测试点）测试 结果下一次比较时恰好用上，这么总测试次数为结果下一次比较时恰好用上，这么总测试次数为n。Fn+2-1 Fn=Fn+1-153/5353
