服务专业公司网站建设服务,推广网站挣钱,网站轮播图怎么保存,过期网站.目录
写在前面#xff1a;
题目#xff1a;92. 递归实现指数型枚举 - AcWing题库
读题#xff1a;
输入格式#xff1a;
输出格式#xff1a;
数据范围#xff1a;
输入样例#xff1a;
输出样例#xff1a;
解题思路#xff1a;
代码#xff1a;
AC
题目92. 递归实现指数型枚举 - AcWing题库
读题
输入格式
输出格式
数据范围
输入样例
输出样例
解题思路
代码
AC
写在最后 写在前面
距离蓝桥杯已经不足一个月了
根据江湖上的传言
蓝桥杯最喜欢考的是深度优先搜索和动态规划
所以蓝桥杯也叫暴搜杯、dp杯
那我备赛当然也就从深度优先搜索也就是所谓的dfs开始。
题目92. 递归实现指数型枚举 - AcWing题库
读题 输入格式
输入一个整数 n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列相邻两个数用恰好 11 个空格隔开。
对于没有选任何数的方案输出空行。
本题有自定义校验器SPJ各行不同方案之间的顺序任意。
数据范围 1 ≤ n ≤ 15
输入样例
3
输出样例 3
2
2 3
1
1 3
1 2
1 2 3
解题思路
这道题是深度优先搜索的经典题目
我们使用深度优先搜索的时候
第一个要注意的点是我们要保证
我们写出的递归结构能够遍历所有情况
在我们初学搜索的时候我们一定要画一个递归搜索树观察
递归非常抽象画图能很好的帮助我们解题。以上递归搜索的基本思路多熟悉总是好的
接下来是具体思路
题目要求我们随机选取输出每种方案而且要求升序输出。
我们根据要求画出对应的搜索树以n3为例
首先是根节点 递归搜索 因为题目要求是升序数组所以从第二个位置开始
就只能填2再下一个就得填3以满足题目要求
继续搜索 如果位置已经使用过了就搜索下一个位置
没有位置就停下。
最后 我们根据画出来的搜索树写代码
代码
//养成好习惯先把常用头文件包了
#include cstdio
#include cstring
#include iostream
#include algorithmusing 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 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果喜欢本文的话欢迎点赞和评论写下你的见解。
如果想和我一起学习编程不妨点个关注我们一起学习一同成长。
之后我还会输出更多高质量内容欢迎收看。
