一、问题描述
按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列(1≤n≤9)，要求所产生的任一数字序列中不允许出现重复的数字。
例如3的全排列为
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
二、题目要求
考察
深度搜索，全排列公式 建议用时15~25min
三、问题分析
1.公式法
看到问题，很自然就会想到C++里面的全排列公式，一步解决。 头文件algorithm，a代表数组名称，n代表数组大小
do{ }while(next_permutation(a,a+n));
2.DFS
第二种方法，深度搜索(DFS)，对于一些大题来说应用广泛，这一题虽然直接使用全排列公式更加合适，今天还是了解一下DFS这种用法。
DFS简单来说就是一只老鼠走迷宫，遇到走不通的道路，往回退一个（俗称回溯）。
与之相对的广度搜索(BFS)更像是，多只老鼠走迷宫，从一个点分别向多个方向发散，直到找到出口。
以全排列为例，设置一个访问数组visited[10]，判断当前数字是否被访问过，0代表没有，1代表有。从1开始深度搜索，未被访问过的数字存入数组，置为1，对下一个数字深度搜索，直到大于给定的n，输出数组里面的数字，进行回溯，以此类推
四、编码实现
1.公式法
//头文件usingnamespacestd; intmain() { inti,n,a[9];//初始化cin>>n;//输入nfor(i=0;i<n;i++) a[i]=i+1;//初始化数组do { for(i=0;i<n;i++)//循环 { printf("%5d",a[i]);//输出数组元素 } cout<<"\n"; }while(next_permutation(a,a+n));//全排列公式return0; }
2.DFS
usingnamespacestd; intn,a[10],visited[10]={0};//初始化定义数字数组和访问数组voidDFS(intk) { inti,j; if(k>n)//大于n { for(j=1;j<=n;j++)//输出数组里面的元素 { printf("%5d",a[j]); } cout<<"\n"; } else { for(i=1;i<=n;i++)//循环判断 { if(!visited[i])//是否访问过 { visited[i]=1;//置为1a[k]=i;//赋值当前i给到kDFS(k+1);//下一步visited[i]=0;//回溯 } } } } intmain() { cin>>n;//输入nDFS(1);//从1开始深搜return0; }
五、输出结果
输入3
