[AcWing]842. 排列数字C++实现dfs模板题,递归思想的解释
递归的难度在于理解递归是如何回退的。
1. 题目
2. 读题(需要重点注意的东西)
思路:
---------------------------------------------------dfs的思想---------------------------------------------------
dfs深度优先遍历的思想比较简单,就是一条路走到底,走到最深点处再回退一步,再看有没有路可以走,没有的话再回退一步,重复此步骤;
dfs的思想比较简单,在此不在过多的赘述,解释代码中实现dfs的递归方法,是本文的主要目的。
---------------------------------------------------递归的思想---------------------------------------------------
递归在于不断调用自己的函数,层层深入,直到遇到递归终止条件后层层回溯,其思想与dfs的思想不谋而合;因此,可以使用递归来实现dfs。
递归的进入比较容易理解,但是递归的回溯是在计算机底层执行的,我们无法看到。因此,递归究竟是如何完成的,成为了理解递归的一大难点,也是理解递归的唯一个一个地个难点。
让我们来看一下这样一个简单的递归程序
#include<iostream>
using namespace std;
int n;
void func(int u){
if(u == 0) return;
cout << "Recursive program goes to the next level --- " << u << endl;
func(u-1);
cout << "Recursive program backtracking --- " << u <<endl;
return;
}
int main(){
cin >> n;
func(n);
return 0;
}
输入3,我们可以看到,它的输出是
我们可以清楚的看到,哪个数字进入了递归,又有哪个数字回溯了。
为什么会产生这样的结果?请看下面这幅图,它解释了递归函数的调用全过程
这样,我们就能理解,为什么首先输出的是Recursive program backtracking — 1了
如果还不是很理解,请看下面的图,我们从u = 0 回退到了u = 1,再直接回退到u = 2,再回退到u = 3
递归程序在回退完成前,return会使得计算机继续依次执行上一层函数调用后的代码。
3. 解法
---------------------------------------------------解法---------------------------------------------------
#include <iostream>
using namespace std;
const int N = 10;
int n;
int path[N]; // 用path数组保存路径上的值
void dfs(int u, int state)
{
if (u == n) // 到叶子节点时
{
for (int i = 0; i < n; i ) printf("%d ", path[i]); // 输出路径上的值
puts(""); // 换行
return;
}
// 在每一层选取没有被用过的数,然后进入下一层
for (int i = 0; i < n; i )
if (!(state >> i & 1)) // 选择一个没有被用过的值放在path[u]中
{
path[u] = i 1;
dfs(u 1, state (1 << i)); // 进入下一层
}
}
int main()
{
scanf("%d", &n);
dfs(0, 0);
return 0;
}
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
6. 总结
dfs模板题,推荐完全背下来。递归的思想也要好好的理解并掌握。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfieajk
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
photoshop蒙版画笔没反应怎么办
PHP中文网 06-24