深入浅出蓝桥杯：算法基础概念与实战应用（三）搜索

算法基础概念与实战应用（三）搜索

文章目录

算法基础概念与实战应用（三）搜索
1.1 深度优先搜索 - DFS
- 1.1.1 枚举⼦集
- 1.1.2 组合型枚举
- 1.1.3 枚举排列
- 1.1.4 全排列问题
1.2 DFS
- 1.2.1 选数
- 1.2.2 ⻜机降落
整体源代码总结

在这里插入图片描述

1.1 深度优先搜索 - DFS

1.1.1 枚举⼦集

在这里插入图片描述

代码如下（示例）：

1#include <iostream>
2using namespace std;
3int n;
4string path; // 记录递归过程中，每⼀步的决策
5void dfs(int pos)
6{
7	if (pos > n)
8	{
9		// path 就存着前 n 个⼈的决策
10		cout << path << endl;
11		return;
12	}
13	// 不选
14	path += 'N';
15	dfs(pos + 1);
16	path.pop_back(); // 回溯，清空现场
17	// 选
18	path += 'Y';
19	dfs(pos + 1);
20	path.pop_back(); // 清空现场
21}
22int main()
23{
24	cin >> n;
25	dfs(1);
26	return 0;
27}
28

1.1.2 组合型枚举

在这里插入图片描述

代码如下（示例）：

1#include <iostream>
2#include <vector>
3using namespace std;
4int n, m;
5vector<int> path;
6// path.size();
7void dfs(int begin)
8{
9	if (path.size() == m)
10	{
11		for (auto x : path) cout << x << " ";
12		cout << endl;
13		return;
14	}
15	for (int i = begin; i <= n; i++)
16	{
17		path.push_back(i);
18		dfs(i + 1);
19		path.pop_back(); // 清空现场
20	}
21}
22int main()
23{
24	cin >> n >> m;
25	dfs(1);
26	return 0;
27}
28

1.1.3 枚举排列

在这里插入图片描述

代码如下（示例）：

1#include <iostream>
2#include <vector>
3using namespace std;
4const int N = 15;
5int n, k;
6vector<int> path;
7bool st[N]; // 标记⼀下哪些数已经选过了
8void dfs()
9{
10	if (path.size() == k)
11	{
12		for (auto x : path) cout << x << " ";
13		cout << endl;
14		return;
15	}
16	for (int i = 1; i <= n; i++)
17	{
18		if (st[i]) continue;
19		path.push_back(i);
20		st[i] = true;
21		dfs();
22		// 恢复现场
23		path.pop_back();
24		st[i] = false;
25	}
26}
27int main()
28{
29	cin >> n >> k;
30	dfs();
31	return 0;
32}
33

1.1.4 全排列问题

在这里插入图片描述

代码如下（示例）：

1#include <iostream>
2#include <vector>
3using namespace std;
4const int N = 15;
5int n;
6bool st[N];
7vector<int> path;
8void dfs()
9{
10	if (path.size() == n)
11	{
12		for (auto x : path)
13		{
14			printf("%5d", x);
15		}
16		cout << endl;
17		return;
18	}
19	for (int i = 1; i <= n; i++)
20	{
21		if (st[i]) continue;
22		path.push_back(i);
23		st[i] = true;
24		dfs();
25		// 恢复现场
26		path.pop_back();
27		st[i] = false;
28	}
29}
30int main()
31{
32	cin >> n;
33	dfs();
34	return 0;
35}
36

1.2 DFS

1.2.1 选数

在这里插入图片描述

代码如下（示例）：

1
2#include<iostream>
3using namespace std;
4const int N = 25;
5int n, k;
6int a[N];
7int ret;
8int path; // 记录路径中所选择的数的和
9bool isprime(int x)
10{
11	if (x <= 1) return false;
12	// 试除法
13	for (int i = 2; i <= x / i; i++)
14	{
15		if (x % i == 0) return false;
16	}
17	return true;
18}
19void dfs(int pos, int begin)
20{
21	if (pos > k)
22	{
23		if (isprime(path)) ret++;
24		return;
25	}
26	for (int i = begin; i <= n; i++)
27	{
28		path += a[i];
29		dfs(pos + 1, i + 1);
30		path -= a[i]; // 恢复现场
31	}
32}
33int main()
34{
35	cin >> n >> k;
36	for (int i = 1; i <= n; i++) cin >> a[i];
37	dfs(1, 1);
38	cout << ret << endl;
39	return 0;
40}
41

1.2.2 ⻜机降落

在这里插入图片描述

代码如下（示例）：

1#include <iostream>
2#include <cstring>
3using namespace std;
4const int N = 15;
5int n;
6int t[N], d[N], l[N];
7bool st[N]; // 标记路径中哪些⻜机已经摆放过
8bool dfs(int pos, int end)
9{
10	if (pos > n)
11	{
12		return true;
13	}
14	for (int i = 1; i <= n; i++)
15	{
16		if (st[i] == true) continue; // 剪枝
17		if (end > t[i] + d[i]) continue; // 剪枝
18		int newend = max(t[i], end) + l[i];
19		st[i] = true;
20		if (dfs(pos + 1, newend)) return true;
21		st[i] = false; // 回复现场
22	}
23	return false;
24}
25int main()
26{
27	int T; cin >> T;
28	while (T--) // 多组测试数据的时候，⼀定要注意清空数据
29	{
30		memset(st, 0, sizeof st);
31		cin >> n;
32		for (int i = 1; i <= n; i++) cin >> t[i] >> d[i] >> l[i];
33		if (dfs(1, 0)) cout << "YES" << endl;
34		else cout << "NO" << endl;
35	}
36	return 0;
37}
38

代码如下（示例）：

整体源代码总结

代码如下（示例）：

《深入浅出蓝桥杯：算法基础概念与实战应用（三）搜索》是转载文章，点击查看原文。