全排列
描述:
输入一个自然数N(1<=N<=9),从小到大输出用1~N组成的所有排列,也就说全排列。例如输入3则输出
123
132
213
231
312
321
输入格式:
输入一个自然数N(1<=N<=9)
输出格式:
N的全排列,每行一个
输入样例:
3
输出样例:
123
132
213
231
312
321
代码:
#include<bits/stdc++.h>
using namespace std;
int a[10],book[10],n;//全局变量在不赋值之前默认是零
void dfs(int step){//step表示站在第几个盒子前面
int i;
if(step==n+1){//如果站在第n+1个盒子前,代表之前的盒子都装满了
for(i=1;i<=n;i++){
printf("%d",a[i]);//输出一种排列
}
printf("\n");
return;//结束这次递归,并返回最近一次调用
}
for(i=1;i<=n;i++){
if(book[i]==0){//表示扑克牌在手上
a[step] = i;//将第i个扑克牌放到第step个盒子里
book[i] = 1;//表示扑克牌已经不再手上
dfs(step+1);//走到下一个盒子前
book[i] = 0;
//将之前的扑克牌收回,表示前面的盒子所有可能性已经全部结束
}
}
return;
}
int main(){
scanf("%d",&n);
dfs(1);//站在一号盒子前
return 0;
}
解析:
利用DFS(深度优先搜索),每次调用自己,并判断几号扑克牌在手中,那个盒子是空着的。最后将其放入盒子中。
Comments | NOTHING