题目描述
输入一个数n,将1~n(1,2,3.....n)的数的所有可能排列一一举出
样例
如输入一个数3
所有的可能排序方式有以下这些:
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
算法dfs
1、定义两个数组,一个存放排列方式,一个作为标记数组,标记从1~n的数中是否被使用过,标记数组初始化为false,表示未曾被使用,一旦使用,标记为true;
2、首先输入一个数n,表示从1~n的数进行排序;
3、深搜,从第0层开始;
4、深搜步骤:
1).每次或者说每层,即排列方案的列,每次都需要遍历一遍1~n数;
2).如果这个数未曾使用,即标记数组为false,则将该数标记为true,表示已使用,然后再将排列方式的该列,即这层,赋值为该数;
3).继续深搜,层数+1
4).恢复现场,即将该层的排列方式改为0,然后将该数重新标记为false
5).直到层数等于n时,即所有数的排列方式举出,则打印出来,然后return,回到上一层
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int a[8];
bool vis[8];
int n;
void dfs(int t)
{
if(t==n)
{
for(int i=0;i<n;i++)
{
cout << a[i] << " ";
}
cout << endl;
return;
}
for(int i=1;i<=n;i++)
{
if(vis[i]==true)
continue;
vis[i]=true;
a[t]=i;
dfs(t+1);
vis[i]=false;
a[t]=0;
}
}
int main()
{
while(cin >> n)
{
memset(vis,false,sizeof(vis));
dfs(0);
}
return 0;
}