目录
- 1 基础知识
- 2 模板
- 3 工程化
1 基础知识
调用dfs()之后表示已经走到头了,需要往回走了(即,回溯),那这时候就要恢复成调用dfs()之前的模样(即,恢复现场)。
不同的搜索顺序,对应着不同的耗时。
2 模板
题目1:输出1,2,3,…,n的全排列,按照字典序输出。
#include
using namespace std;
const int N = 10;
int path[N];
bool st[N];
int n;
void dfs(int u) {//第u位填什么
if (u == n) {
for (int i = 0; i u; ++i) {
cout path[i] " ";
}
cout endl;
}
for (int i = 1; i n; ++i) {
if (!st[i]) {
path[u] = i;
st[i] = true;
dfs(u+1);
st[i] = false;
}
}
return;
}
int main() {
cin >> n;
dfs(0);
return 0;
}
题目2:从1,2,3,…,n中选择m个数,考虑选择的数的顺序(即,这是一个排列问题),请按照字典序输出。
#include
using namespace std;
const int N = 10;
int path[N];
bool st[N];
int n, m;
void dfs(int u) {//第u位填什么
if (u == m) {
for (int i = 0; i u; ++i) {
cout path[i] " ";
}
cout endl;
}
for (int i = 1; i n; ++i) {
if (!st[i]) {
path[u] = i;
st[i] = true;
dfs(u+1);
st[i] = false;
}
}
return;
}
int main() {
cin >> n >> m;
dfs(0);
return 0;
}
题目3:从1,2,3,…,n中选择m个数,不考虑选择的数的顺序(即,这是一个组合问题)。
#include
using namespace std;
const int N = 10;
int path[N];
bool st[N];
int n, m;
void dfs(int u) {//第u位填什么
if (u == m) {
for (int i = 0; i u; ++i) {
cout path[i] " ";
}
cout endl;
}
for (int i = 1; i n; ++i) {
if (!st[i]) {
path[u] = i;
if (u == 0 || path[u-1] path[u]) {
st[i] = true;
dfs(u+1);
st[i] = false;
}
}
}
return;
}
int main() {
cin >> n >> m;
dfs(0);
return 0;
}
题目4:将n个皇后放在n*n的棋盘上,使得n个皇后不能互相攻击到。横、竖、斜线、反斜线。
dfs()方式1:
#include
using namespace std;
const int N = 20;
char g[N][N];
int col[N], dg[N], udg[N];
int n;
void 服务器托管网dfs(int u) {
if (u == n) {
for (int i = 0; i n; ++i) {
for (int j = 0; j n; ++j) {
cout g[i][j];
}
cout endl;
服务器托管网 }
cout endl;
}
for (int i = 0; i n; ++i) { //把Q填入到(u,i)位置处
if (!col[i] && !dg[u+i] && !udg[n-u+i]) {
g[u][i] = 'Q';
col[i] = dg[u+i] = udg[n-u+i] = true;
dfs(u+1);
g[u][i] = '.';
col[i] = dg[u+i] = udg[n-u+i] = false;
}
}
return;
}
int main() {
cin >> n;
for (int i = 0; i n; ++i) {
for (int j = 0; j n; ++j) {
g[i][j] = '.';
}
}
dfs(0);
return 0;
}
dfs()方式2:
#include
using namespace std;
const int N = 20;
char g[N][N];
int row[N], col[N], dg[N], udg[N];
int n;
void dfs(int x, int y, int s) {
if (y == n) {
y = 0;
x++;
}
if (x == n) {
if (s == n) { //如果有n个皇后,则输出此方案
for (int i = 0; i n; ++i) {
cout g[i] endl;
}
cout endl;
}
return;
}
//(x,y)不放皇后
dfs(x, y + 1, s);
//(x,y)可能放皇后
if (!row[x] && !col[y] && !dg[x+y] && !udg[x-y+n]) {
g[x][y] = 'Q';
row[x] = col[y] = dg[x+y] = udg[x-y+n] = true;
dfs(x, y + 1, s + 1);
row[x] = col[y] = dg[x+y] = udg[x-y+n] = false;
g[x][y] = '.';
}
return;
}
int main() {
cin >> n;
for (int i = 0; i n; ++i) {
for (int j = 0; j n; ++j) {
g[i][j] = '.';
}
}
dfs(0, 0, 0);
return 0;
}
3 工程化
暂无。。。
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
相关推荐: 机器人过程自动化(RPA)入门 3. 顺序、流程图和控制流程
到目前为止,我们已经了解了RPA是什么,并且我们已经看到了通过记录任务的活动并运行它来训练UiPath机器人是多么简单。使用记录器的UiPath可以很容易地自动化日常任务。在我们开始自动化复杂的任务之前,让我们学习如何控制从一个到另一个的活动流。 在本章中,我…