没有合适的资源?快使用搜索试试~ 我知道了~
首页C++递归算法详解:计算和与查找应用
本资源是一份关于C++递归算法的教程,标题为"基础算法 第4章 递归算法(C++版)-2020.12.22.pdf",主要针对的是C++编程语言中的递归概念。递归是一种关键的编程技术,它通过函数或过程直接或间接地调用自身来解决复杂问题。章节分为两节,详细介绍了递归的两种形式:直接递归和间接递归。 直接递归是指函数直接调用自身,如`void a()`中`void a()`的调用,这是一种自上而下的解决问题方式。在C++中,递归调用必须包含一个明确的终止条件,例如`if(n==1)`,防止无限循环。间接递归则是指一个函数A调用另一个函数B,B再调用A,如`void a()`调用`void b()`,`void b()`再调用`void a()`,这需要确保最终会到达一个终止状态,避免死循环。 递归算法示例部分提供了两个实例。第一个是计算累加和的问题,通过递归实现`1+2+3+...+(n-1)+n`,满足递归的三个条件:累加性质、有限次数调用以及终止条件(n=1)。递归调用过程中,函数的局部变量和地址存储在栈中,递归结束时,计算机根据栈的信息回溯并计算结果。 第二个问题是查找已排序数组中的元素,当数据有序时,可以采用二分查找。对于递归版本,首先判断输入X是否位于数组的起始位置或结束位置,然后递归地缩小搜索范围,直到找到目标元素或者确定不存在。 递归算法在编程中具有很高的实用性,但同时也需要注意效率问题,因为每次递归调用都会消耗额外的栈空间。因此,理解递归的原理和正确设计终止条件至关重要。这份资料为CSP-J、CSP-S和NOIP级别的学习者提供了实用的C++递归算法教学资源。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/13760346/bga.jpg)
【例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”。
该算法符合递归程序设计的基本规律,可以用递归方法设计。
![](https://csdnimg.cn/release/download_crawler_static/13760346/bgb.jpg)
【参考程序】
#include<iostream>
#include<cstdlib>
using namespace std;
int a[11];
void search(int,int,int);
int main() //主程序
{
int k,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");
}
void search(int x,int top,int bot) //二分查找递归过程
{
int mid;
if (top<=bot)
{
mid=(top+bot)/2; //求中间数的位置
![](https://csdnimg.cn/release/download_crawler_static/13760346/bgc.jpg)
if (x==a[mid]) cout<<“YES”<<endl;
//找到就输出
else
if (x<a[mid]) search(x,mid+1,bot);
//判断在前半段还是后半段查找
else search(x,top,mid-1);
}
else cout<<"NO"<<endl;
}
1.11编程基础之二分查找
http://openjudge.cn/user/741463/
【算法1-6】二分查找与二分答案
https://www.luogu.com.cn/training/111
剩余57页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/f592ccf136744be2b966ff59bc7b59f6_dllglvzhenfeng.jpg!1)
![](https://csdnimg.cn/release/wenkucmsfe/public/img/user-vip.1c89f3c5.png)
dllglvzhenfeng
- 粉丝: 1w+
- 资源: 1869
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 新型矿用本安直流稳压电源设计:双重保护电路
- 煤矿掘进工作面安全因素研究:结构方程模型
- 利用同位素位移探测原子内部新型力
- 钻锚机钻臂动力学仿真分析与优化
- 钻孔成像技术在巷道松动圈检测与支护设计中的应用
- 极化与非极化ep碰撞中J/ψ的Sivers与cos2φ效应:理论分析与COMPASS验证
- 新疆矿区1200m深孔钻探关键技术与实践
- 建筑行业事故预防:综合动态事故致因理论的应用
- 北斗卫星监测系统在电网塔形实时监控中的应用
- 煤层气羽状水平井数值模拟:交替隐式算法的应用
- 开放字符串T对偶与双空间坐标变换
- 煤矿瓦斯抽采半径测定新方法——瓦斯储量法
- 大倾角大采高工作面设备稳定与安全控制关键技术
- 超标违规背景下的热波动影响分析
- 中国煤矿选煤设计进展与挑战:历史、现状与未来发展
- 反演技术与RBF神经网络在移动机器人控制中的应用
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)