1 / 43
文档名称:

《递归算法C语言》.ppt

格式:ppt   大小:517KB   页数:43页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

《递归算法C语言》.ppt

上传人:花开花落 2020/1/5 文件大小:517 KB

下载得到文件列表

《递归算法C语言》.ppt

相关文档

文档介绍

文档介绍:第四章递归算法前面已经介绍了关于递归调用这样一种操作,而递归程序设计是C++语言程序设计中的一种重要的方法,它使许多复杂的问题变得简单,容易解决了。递归特点是:函数或过程调用它自己本身。其中直接调用自己称为直接递归,而将A调用B,B以调用A的递归叫做间接递归。【例1】给定n(n>=1),用递归的方法计算1+2+3+4+...+(n-1)+n。【算法分析】本题可以用递归方法求解,其原因在于它符合递归的三个条件:    (1)本题是累加问题:当前和=前一次和+当前项,而前一次和的计算方法与其相同,只是数据不同s(n)=s(n-1)+n;     (2)给定n,所以是有限次的递归调用;     (3)结束条件是当n=1,则s=1。【参考程序】#include<iostream>usingnamespacestd;intfac(int);//递归函数intmain(){ intt; cin>>t;//输入t的值 cout<<"s="<<fac(t)<<endl;//计算1到t的累加和,输出结果}intfac(intn){ if(n==1)return1; return(fac(n-1)+n);//调用下一层递归}运行程序,当T=5时,输出结果:S=15,其递归调用执行过程是:(设T=3)递归调用过程,实质上是不断调用过程或函数的过程,由于递归调用一次,所有子程序的变量(局部变量、变参等)、地址在计算机内部都有用特殊的管理方法——栈(先进后出)来管理,一旦递归调用结束,计算机便开始根据栈中存储的地址返回各子程序变量的值,并进行相应操作。【例2】设有N个数已经按从大到小的顺序排列,现在输入X,判断它是否在这N个数中,如果存在则输出:“YES”否则输出“NO”。【算法分析】该问题属于数据的查找问题,数据查找有多种方法,通常方法是:顺序查找和二分查找,当N个数排好序时,用二分查找方法速度大大加快。二分查找算法:  (1)设有N个数,存放在A数组中,待查找数为X,用L指向数据的高端,用R指向数据的低端,MID指向中间:  (2)若X=A[MID]输出“YES”;  (3)若X<A[MID]则到数据后半段查找:R不变,L=MID+1,计算新的MID值,并进行新的一段查找;  (4)若X>A[MID]则到数据前半段查找:L不变,R=MID-1,计算新的MID值,并进行新的一段查找;   (5)若L>R都没有查找到,则输出“NO”。   该算法符合递归程序设计的基本规律,可以用递归方法设计。【参考程序】#include<iostream> #include<cstdlib> usingnamespacestd; inta[11]; voidsearch(int,int,int); intmain()//主程序{ intk,x,L=1,R=10; cout<<"输入10个从大到小顺序的数:"<<endl; for(k=1;k<=10;k++) cin>>a[k]; cin>>x; search(x,L,R); system("pause"); } voidsearch(intx,inttop,intbot)//二分查找递归过程{ intmid; if(top<=bot) { mid=(top+bot)/2;//求中间数的位置if(x==a[mid])cout<<"YES"<<endl;//找到就输出 else if(x<a[mid])search(x,mid+1,bot);//判断在前半段还是后半段查找 elsesearch(x,top,mid-1); } elsecout<<"NO"<<endl; }【例3】Hanoi汉诺塔问题有N个圆盘,依半径大小(半径都不同),自下而上套在A柱上,每次只允许移动最上面一个盘子到另外的柱子上去(除A柱外,还有B柱和C柱,开始时这两个柱子上无盘子),但绝不允许发生柱子上出现大盘子在上,小盘子在下的情况,现要求设计将A柱子上N个盘子搬移到C柱去的方法。【算法分析】本题是典型的递归程序设计题。  (1)当N=1时,只有一个盘子,只需要移动一次:A—>C;   (2)当N=2时,则需要移动三次:     A------ 1------>B,     A------ 2------>C,     B------ 1------>C. (3)如果N=3,则具体移动步骤为:假设把第3步,第4步,第7步抽出来就相当于N=2的情况(把上面2片捆在一起,视为一片):

最近更新

二零二五年度沙石运输与供应链金融合作协议 9页

【企业文化】人力资源管理关系企业文化 5页

《过程性考核——研究现状及分析》 5页

《公共部门人力资源管理》选择题题库(珍藏版).. 3页

二零二五年度旅游度假合作经营合同模板 9页

二零二五年度新媒体营销培训委托合同范例 8页

K3产品体系及知识 4页

二零二五年度房屋买卖及家具配置借款合同 8页

AT89C51单片机毕业设计论文 4页

3. 湖州师范学院毕业设计(论文)开题报告 7页

二零二五年度家具电商退货退款销售合同 9页

2025年浙江理工大学006计算机科学与技术学院(.. 4页

2025年安徽师范大学020计算机与信息学院08120.. 4页

2025年上海师范大学学生科研项目立项结果文科.. 5页

二零二五年度员工向公司借款合同争议解决费用.. 9页

00147人力资源管理(一)重点考点详解与解析 4页

#优化电力企业人力资源管理的对策思考 4页

二零二五年度健身私教课程健身教练培训收费协.. 9页

二零二五年度企业临时借调人员服务合同 7页

二零二五年度个人房产抵押借款合同三方执行协.. 8页

书城站台翻新施工合同 8页

2025年度高空作业安全协议合同书(高空平台操.. 9页

2025年度雇佣放羊与草原资源保护合作合同 8页

2025年度重要会议安全保卫服务合同 8页

2025年度车辆借用与车辆租赁保险服务合同 9页

2025年度航空航天散热器铝合金采购合同简易版.. 10页

2025年度绿色施工安全协议书范文 9页

2025年度租船运输费用及船舶租赁保险合同 8页

2025年度知识产权法律事务代理委托合作协议 9页

2025年国考真题《行测》(副省级) 60页