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

最近更新

贸易便利化视角下的湖北自贸试验区建设研究 3页

贝叶斯方法的基因调控网络在医学领域的应用 3页

触摸按键和触摸屏 11页

论互联网金融创新——基于第三方支付支付宝视.. 3页

解放CA1121J型汽车起动故障分析及探讨 3页

装潢专业方向细分情境下设计素描课程优化 3页

表面活性剂的应用 30页

萨中油田二次开发井位优化设计及实施方法 3页

苏二期雨水调蓄池整体设计后评估与优化建议 3页

2025年度个人养老保障计划担保协议 8页

2025年度XX小区供热设施安全评估与供用热力合.. 8页

自然断点法在材料设备分类分级管理评价体系中.. 3页

胡家河矿紧急撤离报警系统的研究与应用 3页

耦合电弧AA-TIG焊电弧压力测量与分析 3页

绿纱矿业选矿厂工艺流程优化实践 3页

经济新常态下中小企业企业文化建设探讨 3页

级配砂石剪切波速与相对密度关系实验研究 3页

粒子群算法在水利工程造价估算中的应用 3页

贵州水利水电职业技术学院赴台学生交流管理办.. 6页

积极推进BIM设计技术在市政工程中的应用 3页

福建尤溪沉积-改造型矿床地质特征及找矿方向 3页

碳化硅质远红外泡沫陶瓷过滤板的制备与性能研.. 3页

矿山设备管理存在的潜在问题及对策探讨 3页

脂肪族羟基磺酸盐高效减水剂 46页

2025年龚姓好听稀少的男孩名字 7页

2025年龙年火命的人啥颜色旺运 4页

2025年龙年信息技术四个字公司起名推荐600个 8页

2025年黑骏马读后感中文500 6页

2025年鲁迅读书笔记500字 13页

2025年高考结束抖音句子200句 21页