赞
踩
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; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。