阅读量:3
文章目录
题目描述
- 给定一个整数
n，将数字1∼n排成一排，将会有很多种排列方法。 - 现在，请你按照字典序将所有的排列方法输出。
输入格式
- 共一行，包含一个整数
n。
输出格式
- 按字典序输出所有排列方案，每个方案占一行。
数据范围
1 ≤ n ≤ 7
基本思路
- 本题是深度优先搜索算法（
DFS）的模板题。深度优先搜索是指在存在多个方向选择时，我们选择一条路走到黑，直到走到一条路的终点；然后，从这条路的终点向前回溯，找到上一个岔路口，走没有走过的那条路，继续一条路走到黑，以此类推。 - 在代码实现上，深度优先搜索算法一般都采用递归的函数形式进行实现。这个函数里面一般分为两种情况，也就是“终点”和“岔路口”两种情况，可以通过简单的
if-else语句进行情况判定。对于岔路口的情况，需要做的事情包括“选择一条当前没有走过的路→以该岔路口为起点递归地进行深度优先搜索→深度优先搜索完成后回到该岔路口，然后将状态恢复到本次深度优先搜索之前”
实现代码
#include <cstdio> // 需要排列的数字个数 int n; // 用一个数组存储排列中的每一个数字 const int N = 10; int arrange[N]; // 用一个布尔数组存储已经完成填充的数字 bool numbers[N + 1]; // 基于深度优先搜索的全排列输出函数，输入的数据为当前已经完成填充的数字个数和需要填充的数字总数 void DFS(int filled, int n) { // 如果已经找到了一个全排列，则将该全排列输出 if(filled == n) { for(int i = 0; i < n; ++ i) printf("%d ", arrange[i]); printf("\n"); } // 还没有找到一个全排列，则从剩下的数字中选择下一个插入排列的数字 else { for(int i = 1; i <= n; ++ i) { // 找到了还没有使用的数字 if(numbers[i] == false) { arrange[filled] = i; numbers[i] = true; DFS(filled + 1, n); numbers[i] = false; } } } } int main(void) { scanf("%d", &n); DFS(0, n); return 0; } 