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片捆在一起,视为一片):

最近更新

二零二五年度大型仓储设备维修保养合同 11页

2025年国家电网招聘之人力资源类模考模拟试题.. 6页

2025年化学与生活论文写 5页

二零二五年度地摊行业展会组织合同 9页

二零二五年度土地承包种植与乡村旅游结合合同.. 10页

2025年临床医生所需知的乳酸代谢优秀资料 3页

2025年《人力资源管理》随堂练习 6页

2025届高考议论文开头写作指导 5页

2025体育论文开题报告范文 5页

2025-2025学年第一学期九年级12月学情调研 4页

二零二五年度合伙人拆伙协议书:关于联合研发.. 10页

0—3岁婴幼儿社区早期教育公共服务体系构建的.. 5页

二零二五年度印刷设备维修合同标的质量 9页

二零二五年度医院绿化景观设计与施工合同 10页

二零二五年度医疗设备合同翻译与市场准入合同.. 9页

二零二五年度化工产品进出口代理合同样本 9页

二零二五年度前台聘用合同双篇——电影院前台.. 8页

二零二五年度农村私人土地流转合同(休闲农业.. 8页

二零二五年度农业贷款融资服务居间合同 9页

二零二五年度儿童用品商标使用许可合同 9页

二零二五年度体育赛事运营法律协议模板 11页

二零二五年度互联网金融服务居间服务合同的法.. 9页

二零二五年度中心金融科技合伙经营合同 9页

二零二五年度5G通信技术专利许可合同书 8页

乳制品冷链配送协议 9页

乒乓球馆装修解约范文 9页

主题公园翻新工程承包 9页

2025年钢材行业绿色供应链合作合同 10页

2025年度鱼养殖保险服务与鱼买卖合同 10页

2025年度高端商务区店面房屋出租合同(含物业.. 8页