




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
递归、递推、分治南京第三十九中学林晖例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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年运输竞争力分析试题及答案
- 物流决策分析试题及答案探讨
- 公寓式精装修住房租赁合同协议
- 厂房租赁合同示范文本
- 产品销售合同协议
- 企业合同风险防范与应对考试复习资料
- 2023九年级数学下册 第2章 圆2.2 圆心角、圆周角2.2.2 圆周角第2课时 圆周角(2)教学实录 (新版)湘教版
- 第21课 冷战后的世界格局-(教学设计)2023-2024学年九年级下册历史部编版(安徽)
- 夏季六防课件
- 3 古诗三首《十五夜望月》(教学设计)2023-2024学年部编版语文六年级下册
- 教师职业道德教育与心理教育相结合的新探索--基于师德培训的实效性
- 液压系统计算公式汇总(EXCEL版)更详细哦
- 色温-XY-UV色坐标换算公式
- 组织行为学组织行为学概论
- TSDPIA 05-2022 宠物猫砂通用技术规范
- 华电《电力安全工作规程》(热力和机械部分)
- 光伏电站工程标准化监理作业手册(完整版)资料
- 《瑞幸咖啡品牌营销策略问题研究8500字(论文)》
- GB/T 6006.3-2013玻璃纤维毡试验方法第3部分:厚度的测定
- GB/T 26939-2011种羊鉴定术语、项目与符号
- GB/T 19189-2011压力容器用调质高强度钢板
评论
0/150
提交评论