2196: 【排列组合问题】排列组合问题

2196: 【排列组合问题】排列组合问题

时间限制: 1 Sec   内存限制: 64 MB

题目描述

“心无界则天地宽，当狂风在你耳边呼啸时，你只当它微风拂面；当暴雨在你眼前倾泻时，你只当它细雨绵绵；当闪电在你头顶肆虐时，你只当它萤火流逝。人，绝不能在逆境面前屈服 ……哎，不说了，又到做操时间了，再晚典狱长要骂人了。”

每天早晨，监狱里的囚犯都必须排成一行，随着“左三圈，右三圈，脖子扭扭，屁股扭扭，早睡早起，咱们来做运动！”的歌声做操。试计算n个囚犯排成一排，共有多少种排列方法并将排列方法打印出来。

输入

一个整数即n。

输出

输出每种方案，每种方案各占一行(字典序)。最后一行为方案数。

样例输入 Copy

2

样例输出 Copy

12

21

2

解析：递归算法。用ans记录答案，程序如下：

#include<bits/stdc++.h>

using namespace std;

int n,tot;

bool a[10005];

int ans[10005];

void dfs(int j){

if(j>n){

for(int i=1;i<=n;i++) printf("%d",ans[i]);

tot++;printf("\n");

return;

}

for(int i=1;i<=n;i++)

if(!a[i]){

ans[j]=i;a[i]=1;

dfs(j+1);

a[i]=0;

}

}

int main(){

memset(a,0,sizeof(a));

cin>>n;tot=0;

dfs(1);

cout<<tot<<endl;

return 0;

}