网站为什么维护,企业做网站预付账款会计分录,专门做外贸的的网站有哪些,成都网站建设推广服务深度优先搜索DFS搜索
DFS#xff1a;从根节点出发#xff0c;寻找子节点#xff0c;到最深层返回到上一层继续递归搜索。
B3621 枚举元组
题目传送
题面
题目描述
n 元组是指由 n 个元素组成的序列。例如 (1,1,2) 是一个三元组、(233,254,277,123)是一个四元组。
给定…深度优先搜索DFS搜索
DFS从根节点出发寻找子节点到最深层返回到上一层继续递归搜索。
B3621 枚举元组
题目传送
题面
题目描述
n 元组是指由 n 个元素组成的序列。例如 (1,1,2) 是一个三元组、(233,254,277,123)是一个四元组。
给定 n 和 k请按字典序输出全体 n 元组其中元组内的元素是在 [1,k] 之间的整数。
「字典序」是指优先按照第一个元素从小到大的顺序若第一个元素相同则按第二个元素从小到大……依此类推。详情参考样例数据。
输入格式
仅一行两个正整数 n,k。
输出格式
若干行每行表示一个元组。元组内的元素用空格隔开。
输入输出样例
输入 #1
2 3
输出 #1
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3题解
排列组合类题目此时使用dfs递归搜索出“最深层”的数据当搜索到一个pos的最深层输出这一次所有数。此时的i是从1开始搜索默认第一个从1开始dfs搜索中数组答案a的pos位置为i继续递归下一个pos1的位置知道搜索到终点。dfs循环中pos到达终点必须写return;否则会出现死循环。
代码
#includebits/stdc.h
using namespace std;int a[100005];
int n,k;
void dfs(int pos){if(posn1){//递归到终点了n个位置都确定了for(int i1;in;i)couta[i] ; coutendl;return;}for(int i1;ik;i){a[pos] i; //第pos个位置为idfs(pos1); //递归下一个位置}
}
int main(){cinnk;dfs(1); //从第1个位置开始搜索
}
B3622 枚举子集
题目传送
题面
题目描述
今有 n 位同学可以从中选出任意名同学参加合唱。
请输出所有可能的选择方案。
输入格式
仅一行一个正整数 n。
输出格式
若干行每行表示一个选择方案。
每一种选择方案用一个字符串表示其中第 i 位为 Y 则表示第 i 名同学参加合唱为 N 则表示不参加。
需要以字典序输出答案。
输入输出样例
输入 #1
3
输出 #1
NNN
NNY
NYN
NYY
YNN
YNY
YYN
YYY
题解
题目中的Y和N可以看作布尔数组方便理解和编写代码。如果是N那么负值为0如果是Y那么负值就是非0的数1。每一种组合的每一个数必须是N或Y所以所有的数都可以用0或1代替。思路和上一道题目一样dfs的搜索是从所有可能的数字选择下一个后递归填充此时pos位置的数值i。如果posn1到了一个数列长度极限判断输出。这里的dfs循环也需要return;代码否则会出现死循环。
要点
dfs() 表示枚挙到第i个人。a数组保存当前枚举情况a们来存第i个人参加还是不参加。当枚举完所有的人就全部输出。dfs(pos) 負責枚挙 alpos」。
代码
#include bits/stdc.h
using namespace std;int n, k;
int a[15];void dfs(int pos) {if(posn1) { // 枚举完所有人for(int i1;in;i){ // 输出方案if(a[i]0)coutN;// 如果是 0 输出 Nelse coutY;// 否则输出 Y}cout endl;return;}for(int i0;i1;i) {a[pos] i; // 将 pos 位填充成 idfs(pos1); // 递归填写后续位置}
}int main() {cin n;dfs(1); // 最先枚举第几个人return 0;
}
