【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,是进入大厂的必备技能。

相关文章
|
1天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
1天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
|
20天前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
14 1
|
1天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!