递推关系的建立及其求解方法课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《递推关系的建立及其求解方法课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 关系 建立 及其 求解 方法 课件
- 资源描述:
-
1、一、递推式的建立一、递推式的建立1、Hanoi塔问题塔问题问题问题: 三柱问题三柱问题问题问题:四柱问题:四柱问题问题问题:m柱问题柱问题2、平面分割问题、平面分割问题问题问题:封闭曲线分割平面:封闭曲线分割平面问题问题:Z分割平面分割平面问题问题:M分割平面分割平面3、Catalan数数问题一:凸问题一:凸n边形的三角形剖分边形的三角形剖分问题二:二叉树数目问题二:二叉树数目问题三:出栈序列问题三:出栈序列4、第二类、第二类Stirling数数 问题一:放置小球问题一:放置小球问题二:集合划分问题问题二:集合划分问题5、其他、其他问题一:集合取数问题问题一:集合取数问题问题二:整数划分问题问
2、题二:整数划分问题二、递推式的求解方法:二、递推式的求解方法:1 递归函数递归函数用数组实现用数组实现求递推式的通项表达式:求递推式的通项表达式: 31、迭加法、迭加法 32、待定系数法、待定系数法 33、特征方程法、特征方程法 34、生成函数法、生成函数法一、递推式的建立一、递推式的建立1、Hanoi塔问题塔问题 问题的提出:问题的提出:Hanoi塔由塔由n个大小不同的圆盘和个大小不同的圆盘和m根木柱根木柱1,2,3.m组成。开始时,这组成。开始时,这n个圆盘由大到小依次套在个圆盘由大到小依次套在1柱上,如图所示。柱上,如图所示。现在要求把现在要求把1柱上柱上n个圆盘按下述规则移到个圆盘按下
3、述规则移到m柱上:柱上:(1) 一次只能移一个圆盘;一次只能移一个圆盘;(2) 圆盘只能在圆盘只能在m个柱上存放;个柱上存放;(3) 在移动过程中,不允许大盘压小盘。在移动过程中,不允许大盘压小盘。求将这求将这n个盘子从个盘子从1柱移动到柱移动到m柱上所需要移动盘子的最少次数柱上所需要移动盘子的最少次数 。问题问题:三柱问题三柱问题设设f(n)为为n 个盘子从个盘子从1柱移到柱移到3柱所需移动的最少盘次。柱所需移动的最少盘次。当当n=1时,时,f(1)=1。当当n=2时,时,f(2)=3。以此类推,当以此类推,当1柱上有柱上有n(n2)个盘子时,我们可以利用下列步骤:个盘子时,我们可以利用下列
4、步骤:第一步:先借助第一步:先借助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)。 所以:所以:f(n)=2 f(n-1)+1 f(n)= 2n-1问题问题
5、:四柱问题:四柱问题【问题分析问题分析】: 令令fi表示四个柱子时,把表示四个柱子时,把i个盘子从原柱移动到目标柱所需的最少移动次数。个盘子从原柱移动到目标柱所需的最少移动次数。 j第一步:先把1柱上的前j个盘子移动到另外其中一个非目标柱(2或3柱均可,假设移到2柱)上,此时3和4柱可以作为中间柱。移动次数为:fj。第二步:再把原1柱上剩下的i-j个盘子在3根柱子(1、3、4)之间移动,最后移动到目标柱4上,因为此时2柱不能作为中间柱子使用,根据三柱问题可知,移动次数为:2(i-j)-1。第三步:最后把非目标柱2柱上的j个盘子移动到目标柱上,次数为:fj。 通过以上步骤我们可以初步得出:通过以
6、上步骤我们可以初步得出:fi = 2*fj+2(i-j)-1j可取的范围是可取的范围是1=jI,所以对于不同的,所以对于不同的j,得到的,得到的fi可能可能是不同的,本题要求最少的移动次数是不同的,本题要求最少的移动次数 fi = min2*fj+2(i-j)-1,其中1=jI const MaxNum = 1000;var n : integer; F3, F4 : array1.MaxNum of double;procedure Init;var i : integer;begin fillChar(F3,sizeOf(F3),0); fillChar(F4,sizeOf(F4),0);
7、 readln(n); F31 := 1; F41 := 1; *F3n 为为Hanoi塔中塔中3根柱子,根柱子,n个盘子的最少移动次数个盘子的最少移动次数 F3n = 2n -1; F4n 为为Hanoi塔中塔中4根柱子,根柱子,n个盘子的最少移动次数个盘子的最少移动次数* for i :=2 to n do F3i := 2*F3i-1 + 1;end; procedure Run;var i, j : integer; minF4i,temp : double;begin for i := 2 to n do begin minF4i :=1e+100; for j := 1 to i-
8、1 do begin temp := 2*F4j + F3i-j; if (temp minF4i) then minF4i := temp; end; *F4i = min(2*F4j + F3i-j);( 1= j =i-1) * F4i :=minF4i; end; writeln(F4n:0:0);end;begin Init; Run;end.问题问题:m柱问题柱问题【问题分析】:设F(m,n)为m根柱子,n个盘子时移动的最少次数:1、先把1柱上的前j个盘子移动到另外其中一个除m柱以外的非目标柱上,移动次数为:fm, j; 2、再把原1柱上剩下的n-j个盘子在m-1根柱子之间移动,最
9、后移动到目标柱m上,移动次数为:fm-1, n-j; 3、最后把非目标柱上的j个盘子移动到目标柱没柱上,移动次数为:fm, j。F(m,n) = min2*F(m, j)+F(m-1,n-j) (1= j n)j2、平面分割问题平面分割问题问题问题问题的提出:设有n条封闭曲线画在平面上,而任何两条封闭曲线恰好相交于两点,且任何三条封闭曲线不相交于同一点,求这些封闭曲线把平面分割成的区域个数。【问题分析】:设f(n)为n条封闭曲线把平面分割成的区域个数。 由图4很容易得出:f(1)=2;f(2)=4。假设当前平面上已有的假设当前平面上已有的n-1条曲线将平面分割成条曲线将平面分割成f(n-1)-
10、个区域,现在加个区域,现在加入第入第n条封闭曲线。第条封闭曲线。第n条曲线每与已有的条曲线每与已有的n-1条曲线相交共有条曲线相交共有2(n-1)个个交点,也就是说第交点,也就是说第n条曲线被前条曲线被前n-1条曲线分割成条曲线分割成2(n-1)段弧线,而每段弧线,而每一条弧线就会把原来的区域一分为二,即增加一个区域,所以共增加一条弧线就会把原来的区域一分为二,即增加一个区域,所以共增加2(n-1)个区域个区域 F(n)=f(n-1)+2(n-1)问题问题问题的提出:一个z形曲线可以把一个平面分割成2部分。如图所示。求n个z形曲线最多能把平面分割成多少部分。写出递推式f(n)。【问题分析】:根
11、据上图容易得出:f(1)=2;f(2)=12。假设平面上已有n-1个z图形把平面分成了f(n-1)个区域。加入第n个z后,单独考虑第n个z的3条边,每一条边和前面的n-1个z共有3(n-1)个交点,即这条边被分成3(n-1)+1部分,所以增加3(n-1)+1个区域,3条边共增加3(3(n-1)+1)个区域。但是第n个z本身有2个交点,故少了2个区域,所以实际增加了3(3(n-1)+1)-2个区域。由以上得出:f(n)=f(n-1)+3(3(n-1)+1)-2 即:f(n)=f(n-1)+9n-8 初始条件:f(1)=2问题问题:M分割平面分割平面问题二的扩展:在问题二的基础上进一步考虑:如果z
展开阅读全文