2139 - 【搜索基础】全排列问题
全排列问题 form.pas/c/cpp
<span style="font-size:18px;"> 输出自然数1~n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复数字。<br />
[输入格式]
<span style="font-size:18px;"> 1<=n<=9<br />
[输出格式]
由1~n组成的所有不重复的数字序列。每行一个序列
[输入样例]
3
[输出样例]
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
<br />
<br />
<br />
Input
Output
Examples
Input
Output
Solution C
#include<stdio.h> int a[1000],v[1000],n; void print(){ int i,total=0; for (i=1;i<=n;i++) if(total==0) printf("%d",a[i],total++); else printf(" %d",a[i]); //将每位输出 printf("\n"); //换行 } void DFS(int dep){ int i; if (dep==n) print(); //如果搜到一个结果输出 dep++; //查找当前要处理位 for (i=1;i<=n;i++) { //枚举当前位 if (v[i]) continue; //如果这个数之前被选过就跳过 v[i]=1; //选中当前位 a[dep]=i;//将当前位存入数组 DFS(dep);//搜索下一位 v[i]=0;//取消选中当前位 } } int main(){ scanf("%d",&n); //读入 DFS(0); //深搜 return 0; system("pause"); //暂停(查看结果) }
Solution C++
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; int n; bool a[11]={0}; int b[11]; int print() { for(int i=1;i<=n-1;++i) { printf("%d ",b[i]); } printf("%d\n",b[n]); } int search(int i) { for(int j=1;j<=n;++j) { if(a[j]==0) { b[i]=j; a[j]=1; if(i==n) { print(); } else { search(i+1); } a[j]=0; } } } int main() { cin>>n; search(1); return 0; }