递推关系的建立及其求解方法

递推关系的建立及其求解方法

ID:38749510

大小:300.00 KB

页数:42页

时间:2019-06-18

递推关系的建立及其求解方法_第1页
递推关系的建立及其求解方法_第2页
递推关系的建立及其求解方法_第3页
递推关系的建立及其求解方法_第4页
递推关系的建立及其求解方法_第5页
资源描述:

《递推关系的建立及其求解方法》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、递推关系的建立及其求解方法王桐林一、递推式的建立0、Fibonacci数列1、Hanoi塔问题问题Ⅰ:三柱问题问题Ⅱ:四柱问题问题Ⅲ:m柱问题2、平面分割问题问题Ⅰ:封闭曲线分割平面问题Ⅱ:‘Z’分割平面问题Ⅲ:‘M’分割平面3、Catalan数问题一:凸n边形的三角形剖分问题二:二叉树数目问题三:出栈序列4、第二类Stirling数问题一:放置小球问题二:集合划分问题5、其他问题一:集合取数问题问题二:整数划分问题二、递推式的求解方法:1.递归函数2.用数组实现3.求递推式的通项表达式:3.1、迭加法3.2、待定系

2、数法3.3、特征方程法3.4、生成函数法三、递推的形式顺推法和倒推法Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。问题:一个数列的第0项为0,第1项为1,以后每一项都是前两项的和,这个数列就是著名的裴波那契数列,求裴波那契数列的第N项。1、Fibonacci数列解答由问题,可写出递推方程算法:F[0]:=1;F[1]:=2;FORi:=2TONDOF[I]:=F[I–1]+F[I–2];总结从这个问题可以看出,在计算裴波那契

3、数列的每一项目时,都可以由前两项推出。这样,相邻两项之间的变化有一定的规律性,我们可以将这种规律归纳成如下简捷的递推关系式:Fn=g(Fn-1),这就在数的序列中,建立起后项和前项之间的关系。然后从初始条件(或是最终结果)入手,按递推关系式递推,直至求出最终结果(或初始值)。很多问题就是这样逐步求解的。对一个试题,我们要是能找到后一项与前一项的关系并清楚其起始条件(或最终结果),问题就可以递推了,接下来便是让计算机一步步了。让高速的计算机从事这种重复运算,真正起到“物尽其用”的效果。递推概念给定一个数的序列H0,H1

4、,…,Hn,…若存在整数n0,使当n=n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hn(0i

5、需要移动盘子的最少次数。问题Ⅰ:三柱问题设f(n)为n个盘子从1柱移到3柱所需移动的最少盘次。 当n=1时,f(1)=1。当n=2时,f(2)=3。以此类推,当1柱上有n(n>2)个盘子时,我们可以利用下列步骤:第一步:先借助3柱把1柱上面的n-1个盘子移动到2柱上,所需的移 动次数为f(n-1)。第二步:然后再把1柱最下面的一个盘子移动到3柱上,只需要1次 盘子。第三步:再借助1柱把2柱上的n-1个盘子移动到3上,所需的移动次 数为f(n-1)。由以上3步得出总共移动盘子的次数为:f(n-1)+1+f(n-1)。所

6、以:f(n)=2f(n-1)+1f(n)=2n-1问题Ⅱ:四柱问题【问题分析】:令f[i]表示四个柱子时,把i个盘子从原柱移动到目标柱所需的最少移动次数。j第一步:先把1柱上的前j个盘子移动到另外其中一个非目标柱(2或3柱均可,假设移到2柱)上,此时3和4柱可以作为中间柱。移动次数为:f[j]。第二步:再把原1柱上剩下的i-j个盘子在3根柱子(1、3、4)之间移动,最后移动到目标柱4上,因为此时2柱不能作为中间柱子使用,根据三柱问题可知,移动次数为:2^(i-j)-1。第三步:最后把非目标柱2柱上的j个盘子移动到目标

7、柱上,次数为:f[j]。通过以上步骤我们可以初步得出:f[i]=2*f[j]+2^(i-j)-1j可取的范围是1<=j

8、,sizeOf(F4),0);readln(n);F3[1]:=1;F4[1]:=1;{*F3[n]为Hanoi塔中3根柱子,n个盘子的最少移动次数F3[n]=2^n-1;F4[n]为Hanoi塔中4根柱子,n个盘子的最少移动次数*}fori:=2tondoF3[i]:=2*F3[i-1]+1;end;procedureRun;vari,j:i

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。