版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第28课 递归算法及程序实现,1.汉诺塔问题。相传古代东方有一座寺庙,庙内有三根座桩,第一根座桩上叠有一摞64个中心带孔、直径各不相同的圆盘片,这些圆盘片叠成塔状,即越上面的盘片的直径越小。要把这64个盘片从第一根座桩搬到第三根座桩上,搬动的规则如下:(1)一次只能从有盘片的座桩上取走一个盘片;(2)被取走的盘片必须马上放到另一根座桩上;(3)任何一根座桩上如果有一个以上盘片,则这些盘片必须呈直径上小下大的塔状。需要搬动多少次才能把64个盘片从第一根座桩搬到第三根座桩上? 2.用递归算法计算n的阶乘n,新课引入,相传古代东方有一座寺庙,庙内有三根座桩,第一根座桩上叠有一摞64个中心带孔、直径各
2、不相同的圆盘片,这些圆盘片叠成塔状,即越上面的盘片的直径越小。要把这64个盘片从第一根座桩搬到第三根座桩上,搬动的规则如下:(1)一次只能从有盘片的座桩上取走一个盘片;(2)被取走的盘片必须马上放到另一根座桩上;(3)任何一根座桩上如果有一个以上盘片,则这些盘片必须呈直径上小下大的塔状。把“从一根座桩上取走一个盘片,放到另一根座桩上”说成是“搬动一次,问题提出,需要搬动多少次才能把64个盘片从第一根座桩搬到第三根座桩上?先将问题缩小化,尝试2个盘、3个盘、4个盘、5个盘等的搬动过程。 Hanoi游戏(点击上图运行体验,3个盘片移动过程演示 4个盘片移动过程演示 5个盘片移动过程演示,经过实践可
3、知,根据规则将3个盘从座柱A搬到座柱C上,最少需要搬动7次,整个移动过程如下,0)是最初的状态,(1)是经1次搬动后的状态,(2)是经2次搬动后的状态,等等。分析(0)、(3)、(4)、(7)这几个过程,搬动3个盘片的过程可分为先将2个盘从座柱A搬到座柱B,然后将最后1个盘从座柱A搬到座柱C,最后再将2个盘从座柱B搬到座柱C。当分析搬动4个盘片的过程时,整个过程可分为先将3个盘从座柱A搬到座柱B,然后将最后1个盘从座柱A搬到座柱C,最后再将3个盘从座柱B搬到座柱C,以此类推,移动n(n1)个盘从座柱A移动到座柱C的过程如下: 步骤:将(n-1)个盘从座柱A搬动到座柱B,在座柱C的帮助下步骤:将
4、第N个盘从座柱A搬动到座柱C步骤:将(n-1)个盘从座柱B搬动座柱C,在座柱A的帮助下移动规则是每次只能搬动一个盘,所以搬动(n-1)个盘时,肯定需要另一个柱子帮助。当n=1时,也就是搬动一个盘,那只要直接将这个盘从座柱A搬到座柱C就可以了,1)汉诺塔的算法流程图,算法Hanoi(n,a,c,b)的含义是:将n个盘从座柱A(源柱)搬至座柱C(目标柱)在座柱B(帮助柱)的帮助下完成,算法的含义十分重要,它说明了过程Hanoi四个参数所表示的含义。这种直接或者间接地调用自身的算法就是递归算法。 递归算法的特点:递归过程一般通过函数或子过程来实现。递归算法的实质:是把问题转化为规模缩小了的同类问题的
5、子问题,然后递归调用函数(或过程)来表示问题的解,2)编写程序代码。 Hanoi过程四个参数分别是盘数,源柱,目标柱,帮助柱,过程完成功能将N个盘从源柱搬动到目标柱在帮助柱帮助下。Sub hanoi(n As Integer, a As String, c As String, b As String) If (n = 1) Then 当只有一个盘时num = num + 1 计算器增加1List1.AddItem (Str(num) + + a + - + c) 搬动一个盘从源柱到目标柱ElseCall hanoi(n - 1, a, b, c) 搬动N-1个盘从座柱A到座柱B,在座柱C帮助
6、下num = num + 1List1.AddItem (Str(num) + + a + - + c)Call hanoi(n - 1, b, c, a) 搬动N-1个盘从座柱B到座柱C,在座柱A帮助下End IfEnd Sub,3)搬动次数计算将n个盘片从座柱A搬到座柱C,完成步骤需要h(n-1)次搬动,完成步骤只需要1次搬动,而完成步骤也需要搬动h(n-1)次。这样,把n个盘片从座柱A搬到座柱C所需的搬动次数 h(4)=2h(3)+1=2(2h(2)+1)+1=2(2(2h(1)+1)+1)+1=2(2(21+1)+1)+1=24-1=15,2(2(21+1)+1)+1恰好是二进制数11
7、11转化为十进制的式子。汉诺塔问题是一个经典的NP问题,对于计算机来说仍然是一个“难”的问题,“难”主要是说程序执行步数随着N的增长呈指数级增长,如果塔上有64个盘,则搬动次数是二进制11111111(64个1)次,换算为十进制数值为264-1=18446744073709551615,目前按每秒可以完成10亿次搬动(大约是230),也需要234秒,大约是198841天,约544年,即使有这样的速度在有生之年是无法看到所有的搬动过程,例:求n的阶乘,计算的阶乘()()(),这是一个规模为的问题。 假定已经计算出了(),则()()。从另一个角度看,规模为的问题(),可以依赖于较小规模(例如规模为
8、)的问题()的解决,依此类推 f(n-1) = (n-1)f(n-2) . 直至 f(2) = 2f(1) 很明显 f(1) = 1 这样可以按相反的次序,一步一步地把f(k)计算出来 (k=2,3,.,n)。这种按同一方法把问题的计算规模逐步变小的过程叫做“递归的展开”,然后逐级代入的过程叫做“递归的返回”。 对于问题f(5),递归的展开是: f(5)=5f(4)f(4)=4f(3)f(3)=3f(2)f(2)=2f(1)f(1)=1递归的返回是f(1)=1f(2)=2f(1)=21=2f(3)=3f(2)=32=6f(4)=4f(3)=46=24f(5)=5f(4)=524=120问题f(5)的计算结果为120,1)算法流程图(点击运行,2)编写程序代码。Function f(n As Integer) As Long 求n的阶乘If n = 1 Thenf = 1 当n=1时,函数f的返回值为1Elsef = n * f(n - 1) 递归地调用函数f来计算(n-1)!的值End IfEnd Function (3)运行调试程序 根据算法流程图,填空完善已经设计好的界面和部分代码的求n阶乘算法,并进行调试,课堂练习,1.用递归方法设计一个算法,计算12+22+n2,参考答案:
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- GB/Z 43963-2024确定额定电压在交流1 000 V以上至2 000 V直流1 500 V以上至3 000 V间设备的电气间隙、爬电距离的数值以及对固体绝缘要求的指南
- 医院餐饮管理方案(2篇)
- 2024年储罐设备项目资金申请报告代可行性研究报告
- 化学反应工程样板-知到答案、智慧树答案
- 2023年自粘壁纸资金需求报告
- 2024年防腐涂料项目资金申请报告代可行性研究报告
- 2023年X射线衍射仪资金需求报告
- 2023年养老资金筹措计划书
- 2023年锌镍蓄电池投资申请报告
- 2024年瑜伽老师项目资金筹措计划书
- 数控铣床作业指导书
- 海运进出口操作流程课件
- 沪教版高中高三数学拓展2《正态分布》说课稿
- 卫生部专科护理领域护士培训大纲
- 上海市大学生安全教育(2022级)学习通课后章节答案期末考试题库2023年
- 2023年广西壮族崇左市宁明县六年级数学第二学期期末考试模拟试题含解析
- 新概念英语电子版
- 缅甸介绍课件
- 督查室年度工作计划参考范文
- 浙江省消防技术规范难点问题操作技术指南(2020版)
- 英美文学经典作品赏析知到章节答案智慧树2023年山东科技大学
评论
0/150
提交评论