【C++】递归,搜索与回溯算法入门介绍和专题一讲解

简介: 【C++】递归,搜索与回溯算法入门介绍和专题一讲解

一、名词解释

1、什么是递归?

递归就是函数自己调用自己。


2、为什么会用到递归?

递归的本质是:

主问题:—>相同的子问题

子问题:—>相同的子问题

3、如何理解递归?

通过:

  • 1)通过递归的细节展开图(前期可以,过了前期一定不能再用了)
  • 2)通过二叉树中的题目
  • 3)宏观看待递归问题(重要)

越往后学越发现,如果只抓住递归的细节展开图,你会发现你根本就学不好递归这个东西,递归的细节展开图只是为了辅助你读过新手期,如果你后面还在用它,那么你往往是学不好递归的。

那么:如何理解宏观看待递归问题这个点呢?

可以分为几个部分:

  • 1)不要再在意递归的细节展开图
  • 2)把递归的函数当成一个黑盒子
  • 3)相信这个黑盒子一定能完成这个任务

4、如何写好递归?

写好一个递归也分为三点:

  • 1)先找到相同的子问题(函数头的设计)
  • 2)只关心某一个子问题是如何解决的(函数体的书写)
  • 3)递归出口

二、搜索vs深度优先遍历vs深度优先搜索vs宽度优先遍历vs宽度优先搜索vs暴搜

1、深度优先遍历vs深度优先搜索

其实,一句话就能概括下来:

遍历是形式,搜索是目的。

所以,我们平时说的深度优先遍历和深度优先搜索,其实他们俩是一样的。

都可以叫做dfs

2、宽度优先遍历vs宽度优先搜索

其实,一句话就能概括下来:

遍历是形式,搜索是目的。

所以,我们平时说的宽度优先遍历和宽度优先搜索,其实他们俩是一样的。

都可以叫做bfs

3、关系图

我们所说的搜索,其实就是暴搜。

4. 搜索问题的拓展

我们刚开始学习搜索时,总以为dfsbfs这两个搜索都只与二叉树有关。其实不然。

从下面的例题开始你会发现,很多东西都能使用dfs进行求解。

三、回溯与剪枝

这两个名词听起来貌似很高大上,其实用一个例子就能解释清楚了。

下面来看一个迷宫问题:

入口和出口如上:我们从入口出发,往右边走遇到墙壁之后,往下走。走到蓝色标记,也就是拐角点的地方后,这就是一个岔路口,此时我们有两种选择:

  • 1)往左边走
  • 2)往右边走

当我们选择往左边走时,如下图:

会遇到墙壁,此时我们就需要原路返回

这个从某一位置出发,一条道走到黑,再沿着原路返回的过程,就叫做回溯

回溯的这条路径,我们用绿色来标记。

此时又走到了蓝色拐点,在这个岔路口我们有三种选择:

1)往上走

2)往左走

3)往右走

可是,我们最初是从上面下来的,然后沿着左边走,走不通之后再返回来的。

所以,我们只有一个选择:往右走。

而这个判断的过程,也就是选择路径的过程,就叫做剪枝。

将往上走的路径剪掉,将往左走的路径剪掉,就是剪枝。

四、专题一

1. 汉诺塔问题

点我直达

算法分析

1.找到相同的子问题:


当n = 1时:

直接将盘子从A柱子挪到C柱子即可。


当n = 2 时

分为三步走:

1)我们需要将盘子a上面的盘子借助C柱子移动到B柱子。

2)将a盘子移动到C柱子上

3)将B柱子上的所有盘子借助A盘子移动到C柱子上。


当n = 3 时

与第二步相同:

分为三步走

1)将a盘子上面的所有盘子借助C柱子移动到B柱子上。

2)将a盘子移动到C柱子上。

3)将B柱子上面的所有盘子借助A柱子移动到C柱子上。

2.只关心某一个子问题如何解决。

所以我们会发现,当n >= 2时,都会执行相同的子问题的操作。操作如下:

  • 1)将a盘子上面的所有盘子通过C柱子挪到B柱子上。
  • 2)将a盘子挪到C盘子上。
  • 3)将B柱子上面的所有盘子挪到C柱子上。

在这整个过程中,你要相信一件事情:

你交给dfs这个函数的任务是:

我要把所有盘子全部借助一个柱子挪到另一个柱子上。

并且要相信dfs这个函数一定能完成这个任务。

这就是宏观看待问题的思路。

3.递归出口

递归出口就是当n = 1时,你会发现跟当n = 其他数的操作步骤是不一样的。

当n = 1时,直接将a盘子移动到C柱子即可。

代码编写

class Solution {
public:
//1.重复的子问题(函数头)
//要将A柱子上面的所有盘子借助B柱子全部转移到C柱子上面
//2.只关心某一个子问题在做什么(函数体)
//3.递归出口
    void dfs(vector<int>& A, vector<int>& B, vector<int>& C,int n) 
    {
        if(n == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }
        dfs(A,C,B,n-1);
        C.push_back(A.back());
        A.pop_back();
        dfs(B,A,C,n-1);
    }
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) 
    {
        int n = A.size();
        dfs(A,B,C,n);
    }
};

总结

提示:这里对文章进行总结:

本文章详细讲解了递归,搜索与回溯算法的入门理解级操作,以及通过一道例题感受一下dfs这种算法的强大之处,关键在于dfs写起来特别简单。

学好dfs,是进入大厂的必备技能。

目录
打赏
0
0
0
0
20
分享
相关文章
算法系列之搜索算法-深度优先搜索DFS
深度优先搜索和广度优先搜索一样,都是对图进行搜索的算法,目的也都是从起点开始搜索,直到到达顶点。深度优先搜索会沿着一条路径不断的往下搜索,直到不能够在继续为止,然后在折返,开始搜索下一条候补路径。
81 62
算法系列之搜索算法-深度优先搜索DFS
|
5天前
|
算法系列之搜索算法-广度优先搜索BFS
广度优先搜索(BFS)是一种非常强大的算法,特别适用于解决最短路径、层次遍历和连通性问题。在面试中,掌握BFS的基本实现和应用场景,能够帮助你高效解决许多与图或树相关的问题。
23 1
算法系列之搜索算法-广度优先搜索BFS
基于SOA海鸥优化算法的三维曲面最高点搜索matlab仿真
本程序基于海鸥优化算法(SOA)进行三维曲面最高点搜索的MATLAB仿真,输出收敛曲线和搜索结果。使用MATLAB2022A版本运行,核心代码实现种群初始化、适应度计算、交叉变异等操作。SOA模拟海鸥觅食行为,通过搜索飞行、跟随飞行和掠食飞行三种策略高效探索解空间,找到全局最优解。
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
36 15
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
36 12
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
60 19
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
54 2
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
|
2月前
|
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
66 4

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等