普及层次第三讲递归递推分治教学课件_第1页
普及层次第三讲递归递推分治教学课件_第2页
普及层次第三讲递归递推分治教学课件_第3页
普及层次第三讲递归递推分治教学课件_第4页
普及层次第三讲递归递推分治教学课件_第5页
已阅读5页，还剩78页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

递归、递推、分治南京第三十九中学林晖例3.1.1背包问题问题一:给定背包容量W和物体种类N,以及每种物体的重量W;,每种物体只有问是否能将背包装满。请统计箱装满的方案数样例输入:54234样例输出:2分析对第n个物体只有两种情况,即取或者不取。若取原问题就转化为search(wan]n1若不取,则转化为search(w,n-1)若w=0则说明能够装满proceduresearchw,n:integer)beginifw=0thenp:=p+1;ifn>=1thenbeginsearch(w-a[nl,n-1)search(w,n-1)end:end:递归转化为非递归递归是算法设计中的一种重要方法它的优势在于能用有限的语句来定义对象的无限集合。对于某些问题,用递归处理起来简单明了,/程序结构清晰精练,但是由于递归处理的过程需占用大量的机时和空间,因而程序的效率低,在必要的时候,需要将递归转化为非递归来处理。非递归算法一般要比递归算法效率高得多求斐波那契数列中的第n个数用递归的方法用非递归的方法beginfunctionfib(ninteger)integer;/f[O]:=0beginf1]:=1;ifn=othenfib:=0elseifn=1thenfib=1readIn(n);fib:=fib(n-1)+fib(n-2)form:=1tondoendfm]:=fm-1]+fm-2]writeIn(f[',n,=,fnDend.递推递推算法:对于一个有规律的数列,我们可以借助已知的项利用特定的关系逐项推算出它的后继项的,…如此反复,直到找到所需的那一项为止,这样的方法称为递推算法。递推算法的首要问题是得到相邻的数据项间的关系(即递推关系)。解决递推问题的一般步骤●建立递推关系式●确定边界条件递推求解例3.2.1NICOMACHUS(尼克马库斯)定理[问题描述]COMACHUS定理:任何一个整数的立方都可以表示成一串奇数的和,例如23=3+5=833=7+9+11=27=13+15+17+19=64表示的规律分析:用Fm)表示n的3次方的数n为奇数:F3)=(32-2)+32+(32+2)=3*3227n为偶数:F4)■■■■口■■■■■■■■■■■■■■■■■■=4+42=64例322:切煎饼●王小二自夸刀工不错,有人放—张大的煎饼在砧板上,问他:“饼不许离开砧板,切100刀最多能分成多少块?”找规律,如下图:切一刀切二刀切三刀切四刀令q(n)为切n刀能分成的块数,从图中可见:q(1)=1+12q(2)=1+1+2=4(3)=1+1+2+3=7q(4)=1+1+2+

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论