鲜花网站建设方案,怎样为网站设计关键词,西安做网站朋朋,wordpress企业营销目录
写在前面#xff1a;
题目#xff1a;93. 递归实现组合型枚举 - AcWing题库
读题#xff1a;
输入格式#xff1a;
输出格式#xff1a;
数据范围#xff1a;
输入样例#xff1a;
输出样例#xff1a;
解题思路#xff1a;
代码#xff1a;
AC
题目93. 递归实现组合型枚举 - AcWing题库
读题
输入格式
输出格式
数据范围
输入样例
输出样例
解题思路
代码
AC
写在最后 写在前面
距离蓝桥杯已经不足一个月了
根据江湖上的传言
蓝桥杯最喜欢考的是深度优先搜索和动态规划
所以蓝桥杯也叫暴搜杯、dp杯
那我备赛当然也就从深度优先搜索也就是所谓的dfs开始。
题目93. 递归实现组合型枚举 - AcWing题库
读题 输入格式
两个整数 nm在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案每行 11 个。
首先同一行内的数升序排列相邻两个数用一个空格隔开。
其次对于两个不同的行对应下标的数一一比较字典序较小的排在前面
例如 1 3 5 7 排在 1 3 6 8 前面。
数据范围 n 0 0 ≤ m ≤ n n (n − m) ≤ 25
输入样例
5 3
输出样例
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
解题思路
这道题是深度优先搜索的经典题目
我们使用深度优先搜索的时候
第一个要注意的点是我们要保证
我们写出的递归结构能够遍历所有情况
在我们初学搜索的时候我们一定要画一个递归搜索树观察
递归非常抽象画图能很好的帮助我们解题。以上递归搜索的基本思路多熟悉总是好的
接下来是具体思路
题目要求是在n个数里选m个输出不同的选择方案
而且要升序排列且字典序小的在前面
我们先画一个递归搜索树理一下思路
首先是根节点以n5m3为例 我的思路是按照位置填数据
因为题目要求升序数组所以第一个数只能是123。 根据题目升序的要求
然后继续往下递归搜索 继续递归搜索 最后一行就是我们需要打印的值
接下来将图形实现成代码
代码
//养成好习惯把常用头文件包了
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;//根据题目要求决定数组大小
const int N 30;int n, m;int st[N];void dfs(int u, int start)
{//如果递归到底if(u m){//输出for(int i 0; i m; i){printf(%d , st[i]);}puts();return;}else{//不重复使用数字for(int i start; i n; i){st[u] i 1;dfs(u 1, i 1);st[u] 0;}}
}int main()
{scanf(%d %d, n, m);dfs(0, 0);return 0;
}
AC 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果喜欢本文的话欢迎点赞和评论写下你的见解。
如果想和我一起学习编程不妨点个关注我们一起学习一同成长。
之后我还会输出更多高质量内容欢迎收看。