P1706 全排列问题

admin · 发表于 2018-5-10 12:06:19

题目描述
输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入输出格式
输入格式：
n(1≤n≤9)

输出格式：
由1～n组成的所有不重复的数字序列，每行一个序列。每个数字保留5个常宽。

输入输出样例
输入样例#1：
3
输出样例#1：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

吴语林 · 发表于 2018-5-12 11:56:06

#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
using namespace std;
int a[20],book[20],n;
void dfs(int cnt)
{
if(cnt==n+1)
{
for(int i=1;i<=n;i++)
printf("%5d",a[i]);
printf("\n");
return;
}
for(int i=1;i<=n;i++)
if(!book[i])
{
book[i]=1,a[cnt]=i;
dfs(cnt+1);
book[i]=0;
}
}
int main()
{
scanf("%d",&n);
dfs(1);
return 0;
}

复制代码

wzd(temp) · 发表于 2018-5-11 21:38:38

#include <cstdio>
#include <cstdlib>
using namespace std;
bool X[10];
int q[10];
int N;
void dfs(int i)
{
if(i==N)
{
for(int ii=0;ii<N;ii++)
printf("%5d",q[ii]);
printf("\n");
return ;
}
for(int j=1;j<=N;j++)
{
if(!X[j])
{
q[i]=j;
X[j]=true;
dfs(i+1);
X[j]=false;
}
}
return ;
}
int main()
{
scanf("%d",&N);
dfs(0);
return 0;
}

复制代码

lyc · 发表于 2018-5-11 22:56:21

#include<iostream>
#include<iomanip>
using namespace std;
int A[10],n;
void dfs(int n,int *A,int js){
if(js == n){
for(int i=0; i<n; i++)
cout<<setw(5)<<A[i];
cout<<endl;
return;
}
else for(int i=1; i<=n; i++){
bool ok = 1;
for(int j=0; j<js; j++)
if(A[j] == i) ok = 0;
if(ok){
A[js] = i;
dfs(n, A, js+1);
}
}
}
int main(){
cin>>n;
dfs(n, A, 0);
return 0;
}

复制代码

diggersun · 发表于 2018-5-11 23:22:21

张笑宇 · 发表于 2018-5-13 17:26:57

#include<iostream>
#include<iomanip>
using namespace std;
int n,a[10],b[10];
void dfs(int x)
{
if (x>=n+1)
{
for (int i=1; i<=n; i++)
cout<<setw(5)<<a[i];
cout<<endl;
return;
}
else
{
for (int i=1; i<=n; i++)
{
if (b[i]==false)
{
b[i]=true;
a[x]=i;
dfs(x+1);
b[i]=false;
}
}
}
}
int main()
{
cin>>n;
dfs(1);
return 0;
}

复制代码

admin · 发表于 2018-5-13 17:59:01

很好基本的pmn 标准的算法

黄煦喆 · 发表于 2018-5-13 20:17:31

#include<iostream>
#include<iomanip>
using namespace std;
int n,b[10],c[10],a[10]= {0,1,2,3,4,5,6,7,8,9};
void ms(int i)
{
if(i>n)
{
for(int j=1; j<i; j++)cout<<setw(5)<<c[j];
cout<<endl;
}
for(int k=1; k<=n; k++)
if(!b[k])
{
c[i]=a[k];
b[k]=1;
ms(i+1);
b[k]=0;
}
}
int main()
{
cin>>n;
ms(1);
return 0;
}

复制代码

diggersun: 你这个A[10] 是干什么用的？

walk_alone · 发表于 2018-5-13 21:22:22

#include <cstdio>
int a[10],n,book[10];
void dfs(int step)
{
if(step==n+1)
{
for(int i=1;i<=n;i++)
printf("%5d",a[i]);
printf("\n");
}
else
for(int i=1;i<=n;i++)
if(book[i]==0)
{
a[step]=i;
book[i]=1;
dfs(step+1);
book[i]=0;
a[step]=0;
}
}
int main()
{
scanf("%d",&n);
dfs(1);
return 0;
}

复制代码

范彦廷提交

liubo · 发表于 2018-5-16 16:48:15

#include<cstdio>
const int maxn = 15;
int n,c[maxn];
void print(int cur){
if(cur == n){
for(int i = 0; i < n;i++)
printf("%5d",c[i]);
printf("\n");
}
else{
for(int i = 1;i <= n;i++){
int ok = 1;
for(int j = 0;j < cur;j++){
if(i == c[j]){ok = 0;break;}
}
if(ok){c[cur] = i;print(cur+1);}
}
}
}
int main(){
scanf("%d",&n);
print(0);
return 0;
}

复制代码

注意精简自己的程序

		自动登录	找回密码
密码			立即注册