您现在的位置是:首页 > Javascript
当前栏目
【AcWing】蓝桥杯备赛-深度优先搜索-dfs(1)
2023-04-18 16:26:02 时间
目录
写在前面:
距离蓝桥杯已经不足一个月了,
根据江湖上的传言,
蓝桥杯最喜欢考的是深度优先搜索和动态规划,
所以蓝桥杯也叫暴搜杯、dp杯,
那我备赛当然也就从深度优先搜索,也就是所谓的dfs开始。
题目:92. 递归实现指数型枚举 - AcWing题库
读题:
输入格式:
输入一个整数 n。
输出格式:
每行输出一种方案。
同一行内的数必须升序排列,相邻两个数用恰好 11 个空格隔开。
对于没有选任何数的方案,输出空行。
本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。
数据范围:
1 ≤ n ≤ 15
输入样例:
3
输出样例:
3
2
2 3
1
1 3
1 2
1 2 3
解题思路:
这道题是深度优先搜索的经典题目,
我们使用深度优先搜索的时候,
第一个要注意的点是,我们要保证,
我们写出的递归结构能够遍历所有情况,
在我们初学搜索的时候,我们一定要画一个递归搜索树观察,
递归非常抽象,画图能很好的帮助我们解题。(以上递归搜索的基本思路,多熟悉总是好的)
接下来是具体思路:
题目要求我们随机选取输出每种方案,而且要求升序输出。
我们根据要求,画出对应的搜索树:(以n=3为例)
首先是根节点:
递归搜索:
因为题目要求是升序数组,所以从第二个位置开始,
就只能填2,再下一个就得填3,以满足题目要求:
继续搜索:
如果位置已经使用过了,就搜索下一个位置,
没有位置就停下。
最后:
我们根据画出来的搜索树写代码:
代码:
//养成好习惯,先把常用头文件包了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
//数组的大小,比题目要求大即可(题目要求n是小于等于15的)
const int N = 20;
//全局变量的数组会把数组元素初始化成0
int st[N];
//这个是需要输入的变量
int n;
void dfs(int u)
{
//数组已经存了n个数,达成条件就可以打印了
if(u == n)
{
for(int i = 0; i < n; i++)
{
//st数组元素 == 1 表示这个位置需要输出
if(st[i] == 1)
{
printf("%d ", i + 1);
}
}
puts("");
return;
}
else
{
//把数组设为1表示该位置写入了数据
st[u] = 1;
dfs(u + 1);
st[u] = 0;
//把数组设为2表示该位置为空
st[u] = 2;
dfs(u + 1);
st[u] = 0;
}
}
int main()
{
scanf("%d", &n);
dfs(0);
return 0;
}
AC !!!!!!!!!!
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果喜欢本文的话,欢迎点赞和评论,写下你的见解。
如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。
之后我还会输出更多高质量内容,欢迎收看。
相关文章
- 前端面试 【JavaScript】— typeof 是否能正确判断类型?
- 前端面试 【JavaScript】— instanceof 能否判断基本数据类型?
- 前端面试 【JavaScript】— 能不能手动实现一下 instanceof 的功能?
- 前端面试 【JavaScript】— Object.is和=== 有什么区别?
- 前端面试 【JavaScript】— JS中类型转换有哪几种?
- 前端面试 【JavaScript】— == 和 ===有什么区别?
- 前端面试 【JavaScript】— 对象转原始类型是根据什么流程运行的?
- JavaScript 的 parseInt() 函数
- javascript实现两个数字进行组合
- JS监听键盘按键
- 大前端开发中的路由管理之五:Flutter篇
- Javascript的DOM操作
- 在Vue项目中使用WebSocket技术
- 新手向:前端程序员必学基本技能——调试JS代码
- React 毁了 Web 开发!
- 「JS 逆向百例」cnki 学术翻译 AES 加密分析
- 商标注册域名后缀用什么?商标和域名有哪些区别?
- 网站建设流程是怎样的?需要看重哪些细节?
- 网站域名商标注册流程是什么?网站域名商标有什么用?
- 如何建设一个实用性强的网站 网站上线后如何运营