洛谷 P1706 全排列问题(深度优先搜索)

文章目录

题目描述

原题链接: P1706

输出自然数 1 到 n 所有不重复的排列,即 n 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 n

输出格式

由 1 ~ n 组成的所有不重复的数字序列,每行一个序列。

每个数字保留 5 个场宽。

输入输出样例

输入
3
输出:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

思路

主要思路:利用搜索,逐个的确定数字,最后输出

看到题意可知这就是高中所学的排列组合。从算法角度来想,这是一道简单的 dfs(深度优先搜索) 题 ,也可理解为 搜索+递归

源代码

#include<iostream>
#include<iomanip>
using namespace std;
const int N = 20;
int n;
bool st[N];		
int path[N];

void dfs(int u) {
	if (u == n) {		//当所要求的的 n 位数填满后进行输出
		for (int i = 0; i < n; i++) {
			cout << setw(5) << path[i]; 	//setw(5)表示数字之间保留五个场宽。括号()里面的数字代表场宽
		}
		cout << endl;
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (!st[i]) {
			path[u] = i;		//将第 u 位填入数字 i
			st[i] = true;		//标记数字 i 已经被使用
			dfs(u + 1);			//对下一位进行填数
			st[i] = false;		//填完 n 位数后,将已标记过的数清空
		}
	} 
}

int main() {
	cin >> n;
	dfs(0);		//传入u为 0,代表从第一位开始填数
	return 0;
}


上一篇:搜索-DFS


下一篇:经典版imanager部署开放需要的防火墙端口