衡水做淘宝网站,拍摄公司形象宣传片,一个网站可以做多少个小程序,清溪网站建设公司碎碎念#xff1a;要开始刷算法题备战蓝桥杯了#xff0c;一切的开头一定是dfs 定义
枚举问题就是咱数学上学到的#xff0c;从n个数里面选m个数#xff0c;有三种题型(来自Acwing) 从 1∼n 这 n个整数中随机选取任意多个#xff0c;输出所有可能的选择方案。 把 1∼n这… 碎碎念要开始刷算法题备战蓝桥杯了一切的开头一定是dfs 定义
枚举问题就是咱数学上学到的从n个数里面选m个数有三种题型(来自Acwing) 从 1∼n 这 n个整数中随机选取任意多个输出所有可能的选择方案。 把 1∼n这 n个整数排成一行后随机打乱顺序输出所有可能的次序 从 1∼n这 n个整数中随机选出 m个输出所有可能的选择方案。
模版
我觉得这三个都可以由同一套板子来做
int path[N];
bool visited[N]
void dfs(int pos, int start, int n, int m)
//pos指的当前枚举位置
//start指开始的值(为了防止有的题目要求递增输入)
//n指的总元素
//m指的从n个里面挑m个进行枚举这是通用的dfs定义,path存储每个位置放的元素的值visited表示该元素是否访问过
逐个分析 对于这个可以看到输出样例中他的一共有多少个数不固定我们可以理解为从n个位置里面挑m个位置本题没有要求以什么形式输出为了规整我默认写的是先1个位置再两个位置再三个位置而且以升序排列其dfs定义为
void dfs(int pos, int start, int m, int n) //这个n又表示有多少个数
{if(pos m){for(int i 1; i m; i) //这个i循环的是位置所以一直到mcout path[i] ;}else{for(int i start; i n; i) //这个i循环的是元素的值所以一直到n{if(!visited[i]){visited[i] false;path[pos] i;dfs(pos1, i1, m , n) //这里是i1,而不是start1//后一个位置的值一定比当前位置值大已知当前位置的值为i则下一位置最低也得是i1}}}
}int main()
{int n;cin n;for(int i 1; i n; i)dfs(1, 1, i, n) //这个就是从n个位置选m个
}第二个 这个就相当于从n个里面选n个也不要求顺序了则start可以当做没有
void dfs(int pos, int n)//这个n既代表位置又代表元素的值
{if(pos n){for(int i 1; i n; i){cout path[i] ;}coutendl;}else{for(int i 1; i n; i){if(!visited[i]){visited[i] true;path[pos] i;dfs(pos1, n); //是去下一个位置visited[i] false;}}}
}
int main()
{cin n;dfs(1);
}
第三个 从n个元素里面选m个元素位置最大也是m个相当于第一种情况的m变式
void dfs(int pos, int start, int n, int m) //开始的值当前位置
{if(pos m) {for(int i 1; i m; i)cout path[i] ;cout endl;}else{for(int i start; i n; i){if(!visited[i]){visited[i] true;path[pos] i;dfs( pos1, i1, n,m);visited[i] false;}}}
}int main()
{cin n m;dfs(1, 1, n, m);return 0;
}总结
边界条件比较的是位置 下面的for循环是循环的元素的值所以边界有时候不一样如果要以元素的递增则i start 后续要变化其余的剪枝回溯现场就不作解释了csdn上有很多讲的超级明白的我在这里就是对这三种题型做个总结
