版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
递归、递推、分治南京第三十九中学林晖例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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2027届安徽皖南八校高三上第一次联考地理试卷含答案
- 2026事业单位工勤技能-广西-广西水利机械运行维护工四级(中级工)历年参考题库含答案详解
- 2026事业单位工勤技能-广东-广东计算机文字录入处理员一级(高级技师)历年参考题库含答案详解
- 2026事业单位工勤技能-广东-广东机械冷加工四级(中级工)历年参考题库含答案详解
- 2026事业单位工勤技能-广东-广东动物检疫员二级(技师)历年参考题库含答案详解
- 2026事业单位工勤技能-山西-山西兽医防治员四级(中级工)历年参考题库含答案详解
- 2026事业单位工勤技能-山东-山东管道工一级(高级技师)历年参考题库含答案详解
- 2026事业单位工勤技能-山东-山东广播电视天线工四级(中级工)历年参考题库含答案详解
- 2026事业单位工勤技能-山东-山东仓库管理员二级(技师)历年参考题库含答案详解
- 2026事业单位工勤技能-安徽-安徽热力运行工二级(技师)历年参考题库含答案详解
- 2026年国家电网统招考试管理类专业知识模拟试题及答案(十四)
- 第7课 神奇的世界 第1课时 课件(内嵌视频)2026-2027学年道德与法治四年级上册统编版
- 2026年环境集团招聘题库(含答案)
- T/DZJN 481-2025冷凝式家用燃气快速热水器冷凝水雾化绿色排放分级评价
- 2026年低压电工最-新题库及答案(可下载)
- 职业健康检查质量手册
- 2026年中国煤炭科工集团校园招聘面试攻略与技术问答
- T∕CPCPA 0017-2026 托育机构婴幼儿回应性照护服务规范
- 建筑设计工程安全管理制度
- 2026年山东省公务员考试试题及答案
- 县太极协会财务制度
评论
0/150
提交评论