题目链接

可以通过参考一道例题来加深对dfs的认知和学习

题意描述

按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数

字序列中不允许出现重复的数字。

输出格式

由 1 ∼ n 组成的所有不重复的数字序列，每行一个序列。每个数字保留 5 个场宽。

数据范围：1<= n <= 9

题目分析

输入：

输出：

    1    2    3

    1    3    2

    2    1    3

    2    3    1

    3    1    2

    3    2    1

观察输出样例可知，5个场宽输出的意思是每个数输出时占5个位置且右对齐，就是以

" %5d "格式输出

接着分析题目，求全排列，其实可以深搜，也就是dfs。

解题思路

算法分析

我们以 n = 3 为例，可以构造一颗搜索树来进行搜索。

如图所示：对一个位置进行查找，把之前没有用过的数填上去，接着对下一个位置进行

相同操作，知道每个位置填满数为止。

程序实现

我们总结一下在上一部分中的思路在程序中如何实现。

先定义两个数组，一个是用来存放解的，一个是用来标记该数是否用过。

我们可以先写一个用于打印的函数print()，每当深搜时找到一个符合条件的解时，则

print()一下，输出这个解（注意题目输出要求）。

接下来就是写深搜的函数了。主要思路：先判断格子是否填满了，如果填满，则print()一下。

如果没有填满，则开始循环，在循环中先判断当前填的数是否用过，如果没有，则填

入，搜索下一格。

代码如下

#include <iostream>

using namespace std;

const int  N = 10;

int n;

int a[N];

bool q[N];

void dfs(int x){

	if(x == n){

		for(int i = 0 ; i < n ; i++)

		printf("%5d",a[i]);

		puts("");

	}

	for(int i = 1 ; i <= n ; i++){

		if( !q[i] ){

			a [x] = i;

			q[i] = true ;

			dfs(x+1);

			q[i] = false ;

			a[x] = 0;

  		}

	}

}

int main()

{

	cin >> n ;

	dfs(0);

	return 0;

 }

巴特西

dfs学习笔记

题意描述

题目分析

解题思路

代码如下

最新文章

热门文章