- 1、本文档共14页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
递推--递归算法 递归的概念与基本思想 递归过程是借助于一个递归工作栈来实现的 问题向一极推进,这一过程叫做递推; 而问题逐一解决,最后回到原问题,这一过程叫做回归。 递归的过程正是由递推和回归两个过程组成。 递归定义必须是有确切含义的,即一步比一步简单,最终是有终结的,决不能无限循环下去。 递归与递推既有相似点又有不同点,相同点是数据元素间的关系可以用抽象的、严格的公式表示出来,且不论是递推还是递归,都具有边界条件。不同点是递推是从边界条件出发,通过递推关系求f(n)的值,从边界到目标解的过程清楚直观;而递归是从函数自身出发来达到边界条件,在通往边界的递归过程中,系统要用推栈把每次调用的中间结果保存下来,供递归返回时使用(出栈),而编写出来的程序却是高度概括的,这一复杂的过程由操作系统来完成。 一个递归算法,本质上是将较复杂的处理归结为较简单的处理,……直到最简单的处理。从实际问题中抽象出递归定义和边界条件地过程是一种归纳, 通过这种归纳方式能使一个蕴含递归关系且结果复杂的程序变得简洁精炼。特别是在难于找到从边界到解的全过程的情况下,如果把问题推进一步,其结果仍维持原问题的关系,只是规模减小了,则采用递归算法比较适合。但递归算法也有其致命的缺点:执行的效率低,尤其在边界条件设置不当的情况下,极有可能陷入死循环或内存溢出的情况。 一、直线的交点数 [问题]平面上有n条直线,且无三线共点,问这些直线能有多少种不同的交点数。 输入:n(n=20). 输出:若干行,列出所有相交方案,其中每一行为一个可能的交点数。 [问题分析] 我们将n条直线排成一个序列。直线2与直线1最多有一个交点;直线3与直线1和直线2最多有2个交点,……,直线n与其它n-1条直线最多有n-1个交点。由此得出n条直线互不平行且无三线共点的最多交点数max=1+2+……+(n-1)= ,但本题远没有这么简单。 设数组g[1..max],g[i]=0表示交点数i不存在,g[i]=1表示交点数i存在(0≤i≤max) 容易列举出i=1,2,3的情形,下面分析n=4的情况: (1)四条直线全部平行,无交点,g[0]=1; (2)三条直线平行,交点数为(n-1)×1+0=3 g[3]=1; (3)二条直线平行。这两条直线与另外两条直线间的交点数为(n-2)×2=4。而另外两条直线既能平行亦能相交,因此交点数分别为: (n-2)×2+0=4 g[4]=1 (n-2)×2+1=5 g[5]=1 (4)四条直线互不平行。交点数为(n-1)×1+3条直线的相交情况: (n-1) ×1+0=3 g[3]=1 (n-1)×1+2=5 g[5]=1 (n-1)×1+3=6 g[6]=1 即n=4时,有0、3、4、5、6个不同的交点数。 问题:设有一块正方形的钢板,现需将它分成n个小正方形。例如,当: n=2 不可能有解。 n=3 不可能有解。 n=4 可分成4个小正方形钢板。 n=5 不可能有解。 n=6 即一个大的加五个小的。 n=7 即三个较大的加四个小的。 n=8 即一个大的加七个小的。 问题:任给n,求出分成n个小正方形的方法。 四、递推的应用(博弈问题) 走直线棋。有如下所示的一个编号为1到n的方格: 现由计算机和人进行人机对奕,从1到n,每次可以走k个方格,其中k为集s={a1,a2, a3,....am}中的元素(m=4),规定谁最先走到第n格为胜,试设计一个人机对奕方案,摸拟整个游戏过程的情况并力求计算机尽量不败。 * * 递归的应用 解决有哪些信誉好的足球投注网站问题 处理递归定义或解决方法为递归方式的问题 实现分治思想 用于输出动态规划的中间过程 递归不仅可用于计算、计数,而且还可用于枚举,即把所有具有某种特性的对象完全枚举出来,关键是如何从输入参数与输出结果之间的对应关系中归纳出递归公式和边界条件。与递推一样,归纳探究出递归公式是解决此类问题的关键。 从以上分析中,得到: m条直线的交点方案=(m-r)条平行线与r条直线交叉的交点数+r条直线本身的交点方案=(m-r)×r+r条直线本身的交点方案 (1≤r≤m) 上式说明:计算不同交点方案的问题是递归的,描述成如下递归算法: procedure try(m,j) {m为直线,j为交点数} begin if m0 {若直线存在,则递归计算所有的交叉情况} then for r:=m downto 1 do try(m-r,j+r*(m-r)) else g[j]=1 {否则确定m条直线存在j个交点}
您可能关注的文档
- 导论 西方经济思想史 教学课件.ppt
- 导体的静电平衡.ppt
- 导游词莆田湄洲妈祖文化.doc
- 导游英语情景口语Item 14-3 导游还是导购.ppt
- 导游英语情景口语Item 16-1 再见,中国.ppt
- 道路工程常用指标单价-路面工程 15年9月.docx
- 道路工程常用指标单价-通用、路基工程 15年9月.docx
- 德福莱私募债券募集说明书.doc
- 德国和中国 漫画比较.ppt
- 德国会展王国.doc
- 2024年全自动杠杆式电动起子项目可行性研究报告.docx
- 2024年牙缸项目可行性研究报告.docx
- 2024至2030年中国塑料封面数据监测研究报告.docx
- 2024年中国不锈钢储存容器市场调查研究报告.docx
- 2024年尪痹颗粒项目可行性研究报告.docx
- 2024年中国两火特大圆庭院灯市场调查研究报告.docx
- 2024年汽车里程表传感器塑件项目可行性研究报告.docx
- 2024年中国真空破坏器市场调查研究报告.docx
- 2024至2030年中国空调板链线数据监测研究报告.docx
- 2024年03月黑龙江佳木斯汤原县卫生健康局所属事业单位高校现场招考聘用16人笔试历年典型考题与考点.docx
文档评论(0)