计算机算法设计与分析 第2章 递归与分治策略 (笔记)

简介: 计算机算法设计与分析 第2章 递归与分治策略 (笔记)

第2章 递归与分治策略

 

2.1 递归的概念

直接或间接调用自身为递归。

采用递归的目的(思路)是将一个较大(或较复杂)的问题分解成较小的相同问题。

使用递归方法时,一定要设置结束递归的边界条件。

递归的实现的关键是建立递归调用工作栈。(但使用时并不需要我们去建立,系统自动进行这个操作。)

递归的优点是形式简单,缺点是运行效率低(多次调用函数耗费大量时间、空间,问题规模较大时无法在规定时间内完成)。

例-阶乘】 阶乘函数 n!

可用递归函数定义:

n! = 1          ,n=0

      n(n-1)!  ,n>0

递归函数必须有非递归定义(直接给定)的初始值

第一式给出初始值,第二式给出用较小自变量表示较大自变量的函数值的式子。

用C++表示:

int factorial(int n) {
  if( n == 0)
    return 1;
  else
    return n*factorial(n-1);
}

例-斐波那契数列

数列1,1,2,3,5,8,13,21,...为斐波那契数列。

F(n) = 1                    , n = 0或1

F(n) = F(n-1)+F(n-2)  n>1

C++表示:

int fibonacci(int n){
  if (n<=1)
    return 1;
  else
    return fibonacci(n-1)+fibonacci(n-2);
}


【例-Hanoi塔问题】

汉诺塔问题是一个经典的可用递归解决的问题。

问题简述:

设有3个塔座,记为a,b,c

开始时a上一共叠有n个圆盘,圆盘从下到上,由大到小地叠在一起。

要求把a上的n个圆盘移到b上,仍按照上小下大的顺序叠放。

规则是每次只能移动一个盘子,且大盘子不能压在小盘子上。

 

使用递归方法分析这个问题:

当n=1时,将这个盘子放在b上即可

n>1时,先把n-1个盘子放在c上,再把最大的那个放在b上,接着把n-1个盘子放在b上。

void hanoi(int n, int a, int b, int c) {  //把a上的n个圆盘移到b上
    if(n>0){               //n>0,(有盘子时执行下面操作,n=0就放完了,结束)
        hanoi(n-1,a,c,b);  //把a上的n-1个圆盘移到c上,b是中转站
        move(a,b);         //移动剩下的那个大圆盘
        hanoi(n-1,c,b,a);  //将c上的n-1个圆盘移到b上,a是中转站
    }
}

2.2 分治法的基本思想

分治法的基本思想是将一个规模为n的问题 分解为 k个规模较小的子问题。子问题相互独立与原问题相同

递归地解这些子问题,然后将各子问题地解合并得到原问题的解。

 【例-二分搜索技术】

给定以排序的n个元素a[0,n-1],要在这n个元素里找一特定元素x。

若使用顺序搜索方法逐个比较x和a[]中的元素,最坏情况下要对比完所有的n个元素,时间复杂度O(n)。


使用二分搜索可在O(logn)时间完成搜索。基本思想如下:

将n个元素分为个数相当的两半,取a[n/2]与x比较,

若x= a[n/2],找到x,算法终止;

若x<a[n/2],则x在a[n/2]左侧,在a[n/2]左侧搜索;

若a>[n/2],x在a[n/2]右侧,在a[n/2[右侧搜索。

 

template<class Type>
int BinarySearch(Type a[],const Type& x,int n){
    int left = 0;
    int right = n-1;
    while(left<=right){
        int middle = (left+right)/2;
        if(x==a[middle])
            return middle;
        if(x>a[middle])
            left = middle+1;
        if(x<a[middle])
            right = middle-1;
    }
    return -1;
}


相关文章
|
3天前
|
算法 开发者 Python
惊呆了!Python算法设计与分析,分治法、贪心、动态规划...这些你都会了吗?不会?那还不快来学!
【7月更文挑战第10天】探索编程巅峰,算法至关重要。Python以其易读性成为学习算法的首选。分治法,如归并排序,将大问题拆解;贪心算法,如找零问题,每步求局部最优;动态规划,如斐波那契数列,利用子问题解。通过示例代码,理解并掌握这些算法,提升编程技能,面对挑战更加从容。动手实践,体验算法的神奇力量吧!
24 8
|
2天前
|
算法 搜索推荐 编译器
算法高手养成记:Python快速排序的深度优化与实战案例分析
【7月更文挑战第11天】快速排序是编程基础,以O(n log n)时间复杂度和原址排序著称。其核心是“分而治之”,通过选择基准元素分割数组并递归排序两部分。优化包括:选择中位数作基准、尾递归优化、小数组用简单排序。以下是一个考虑优化的Python实现片段,展示了随机基准选择。通过实践和优化,能提升算法技能。**
8 3
|
3天前
|
算法 Python
Python算法高手进阶指南:分治法、贪心算法、动态规划,掌握它们,算法难题迎刃而解!
【7月更文挑战第10天】探索Python算法的精华:分治法(如归并排序)、贪心策略(如找零钱问题)和动态规划(解复杂问题)。通过示例代码揭示它们如何优化问题解决,提升编程技能。掌握这些策略,攀登技术巅峰。
|
4天前
|
机器学习/深度学习 数据采集 算法
Python基于Lasso特征选择、GM算法和SVR回归算法进行财政收入影响因素分析及预测
Python基于Lasso特征选择、GM算法和SVR回归算法进行财政收入影响因素分析及预测
|
4天前
|
数据采集 算法 搜索推荐
Python基于RFM模型和K-Means聚类算法进行航空公司客户价值分析
Python基于RFM模型和K-Means聚类算法进行航空公司客户价值分析
|
2天前
|
算法 数据挖掘
MATLAB数据分析、从算法到实现
MATLAB数据分析、从算法到实现
|
8天前
|
机器学习/深度学习 算法 调度
Matlab|基于改进鲸鱼优化算法的微网系统能量优化管理matlab-源码
基于改进鲸鱼优化算法的微网系统能量管理源码实现,结合LSTM预测可再生能源和负荷,优化微网运行成本与固定成本。方法应用于冷热电联供微网,结果显示经济成本平均降低4.03%,提高经济效益。代码包括数据分段、LSTM网络定义及训练,最终展示了一系列运行结果图表。
|
8天前
|
算法
基于Dijkstra算法的最优行驶路线搜索matlab仿真,以实际城市复杂路线为例进行测试
使用MATLAB2022a实现的Dijkstra算法在城市地图上搜索最优行驶路线的仿真。用户通过鼠标点击设定起点和终点,算法规划路径并显示长度。测试显示,尽管在某些复杂情况下计算路径可能与实际有偏差,但多数场景下Dijkstra算法能找到接近最短路径。核心代码包括图的显示、用户交互及Dijkstra算法实现。算法基于图论,不断更新未访问节点的最短路径。测试结果证明其在简单路线及多数复杂城市路况下表现良好,但在交通拥堵等特殊情况下需结合其他数据提升准确性。
|
13天前
|
算法 安全 数据库
基于结点电压法的配电网状态估计算法matlab仿真
**摘要** 该程序实现了基于结点电压法的配电网状态估计算法,旨在提升数据的准确性和可靠性。在MATLAB2022a中运行,显示了状态估计过程中的电压和相位估计值,以及误差随迭代变化的图表。算法通过迭代计算雅可比矩阵,结合基尔霍夫定律解决线性方程组,估算网络节点电压。状态估计过程中应用了高斯-牛顿或莱文贝格-马夸尔特法,处理量测数据并考虑约束条件,以提高估计精度。程序结果以图形形式展示电压幅值和角度估计的比较,以及估计误差的演变,体现了算法在处理配电网状态估计问题的有效性。
|
10天前
|
数据采集 存储 算法
基于BP算法的SAR成像matlab仿真
**摘要:** 基于BP算法的SAR成像研究,利用MATLAB2022a进行仿真。SAR系统借助相对运动合成大孔径,提供高分辨率图像。BP算法执行回波数据预处理、像素投影及图像重建,实现精确成像。优点是高精度和强适应性,缺点是计算量大、内存需求高。代码示例展示了回波生成、数据处理到插值显示的全过程。