- 1、本文档共98页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
第08单元_算法引论
6 7 5 1 3 2 4 下面的任务:用刚才介绍的方法,对 5 左、右两侧的两段数据,分别进行排序。 a 0 1 2 3 4 5 6 下标 × × × 1 3 2 4 a 0 1 2 3 4 5 6 下标 l r 6 7 × × × × × a 0 1 2 3 4 5 6 下标 l r 7 6 5 4 3 2 1 最后的结果: a 0 1 2 3 4 5 6 下标 作业题:快速排序的编程实现。 - END - 那么如何使用递归算法来解决一个实际的 问题呢?求阶乘的例子是非常简单的,递归形 式已知。对于一个真正的实际问题,它的递归 形式不是那么明显的,难以找到一种合适的递 归形式来实现它,需要很强的逻辑分析能力和 抽象的能力。 递归算法的类型 递归算法可以分为两种类型: 基于分治策略的递归算法; 基于回溯策略的递归算法。 8.5.2 基于分治策略的递归算法 分而治之(divide-and-conquer)的算法 设计思想: Divide:把问题划分为若干个子问题; Conquer:以同样的方式分别去处理各个子问题; Combine:把各个子问题的处理结果综合起来,形成最终的处理结果。 fact(3) fact(2) 调用 fact(1) 调用 …… 调用 调用 …… 调用 调用 …… 调用 调用 1. 指数运算 计算xn,其中n为一个非负整数 问题描述: 简单的方法:xn = x * x * … * x (n个x相乘), 因此可以采用一个循环语句来实现,算法的 时间复杂度为O(n)。 如何来设计相应的递归算法? 由xn = x * x * … * x, 可知xn = x * xn-1,且x0 =1.0 这就是递归算法的递归形式和递归边界,据 此可以编写出相应的递归函数。 // 此函数返回x^n double power_2(double x, unsigned int n) { if(n == 0) return(1.0); return(x * power_2(x, n-1)); } 递归算法 x3 调用 x2 调用 x1 调用 x0 返回 返回 返回 此递归算法的时间复杂度是什么? O(n) 能否设计出一种更好的递归算法,以降低 时间复杂度? 递归算法的设计包括:递归形式和递归边界 递归边界:即x0 =1.0 递归形式: // 此函数返回x^n double power_3(double x, unsigned int n) { double semi; if(n == 0) return(1.0); semi = power_3(x, n / 2); // 计算xn/2或x(n-1)/2 if(n % 2 == 0) return(semi * semi); else return(semi * semi * x); } 新的递归算法 时间复杂度? 相传在古印度的Bramah庙中,有位僧人整天把三根柱子上的金盘倒来倒去,原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中遵守以下规则:每次只允许移动一只盘,且大盘不得落在小盘上。有人会觉得这很简单,但真的动手移盘就会发现,若每秒移动一只盘子,按照上述规则将64只盘子从一根柱子移至另一根柱子上,所需时间约为5800亿年 2. 汉诺(Hanoi)塔问题 应该用递归算法来解决。但怎么样寻找洋娃娃?怎么样寻找递归的形式?从思路上还是先从最简单的情况分析起,搬一搬看,慢慢理出思路。 A 1、在A柱上只有一只盘子,假定盘号为1,这时 只需将该盘从A搬至C,一次完成,记为: move from A to C B C 1 1 1 1 1 1 1 A 2、在A柱上有两个盘子,1为小盘,2为大盘 第 1 步将1号盘从A移至B, 这是为了让2号盘能移动 第 2 步将2号盘从A移至C; 第 3 步再将1号盘从B移至C; 这三步记为: move from A to B; move from A to C; move from B to C; B C 2 1 1 2 1 3、在A柱上有三个盘子, 从小到大分别为1号, 2号, 3号 第 1 步将1号盘和2号盘从A移至B, 使3号盘能移动 第 2 步将3号盘从A移至
您可能关注的文档
- 第 二十二单元 非货币性资产交换.ppt
- 第 9 单元 差错控制编码.ppt
- 必修四+三角函数的周期性.ppt
- 八、大气的垂直分层与对流层大气的热状况.ppt
- 八年级英语下module8 public holidays课件外研版.ppt
- 八年级数学 多项式课件 北师大版.ppt
- 八年级上册物理_____光的折射课件.ppt
- 必修一 第二单元 基本初等函数(ⅰ) 对数函数及其性质 指数函数与对数函数的关系.ppt
- 八年级物理第五单元电流与电路.ppt
- 第01单元 序列的统计量、检验和分布.ppt
- 广播电视播音员主持人全真模拟模拟题附答案详解(预热题).docx
- 危险化学品安全作业题库检测试题打印附参考答案详解【夺分金卷】.docx
- 教师资格考前冲刺练习试题含答案详解【夺分金卷】.docx
- 广播电视播音员主持人全真模拟模拟题(典型题)附答案详解.docx
- 教师资格考试综合练习附完整答案详解【精选题】.docx
- 人教版四年级下册数学期末测试卷1套.docx
- 2025广播电视播音员主持人自我提分评估完整版附答案详解.docx
- 2025年广播电视播音员主持人考试综合练习附答案详解【巩固】.docx
- 2025年教师资格能力提升B卷题库(夺冠)附答案详解.docx
- 2025年教师资格试卷及参考答案详解【满分必刷】.docx
最近下载
- 2025年公考:综合应用--讲义.pdf VIP
- 【真题】2024年云南省特岗教师初中物理学科专业知识试卷全解析版.pdf
- 党员档案核查情况登记表.docx VIP
- 固定式压力容器安全技术监察规程.doc VIP
- 财务会计(初级) 任务一 资产负债表的编制 课件-资产负债表的编制.pptx VIP
- 高耐磨性数控机床主轴的热处理工艺设计.docx VIP
- DB43T1714-2019 自驾游领队服务规范.pdf VIP
- 小学三年级数学口算脱式竖式应用题(2024年整理).pdf VIP
- 助培理论考核试题题库及答案.docx VIP
- DL_T 5041-2023 火力发电厂厂内通信设计技术规定.docx VIP
文档评论(0)