华师一附中OI组

标题: P1706 全排列问题 [打印本页]
作者: admin    时间: 2018-5-10 12:06
标题: P1706 全排列问题
题目描述
输出自然数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

作者: wzd(temp)    时间: 2018-5-11 21:38
  1. #include <cstdio>
  2. #include <cstdlib>
  3. using namespace std;
  4. bool X[10];
  5. int q[10];
  6. int N;
  7. void dfs(int i)
  8. {
  9.         if(i==N)
  10.         {       
  11.                 for(int ii=0;ii<N;ii++)
  12.                         printf("%5d",q[ii]);
  13.                 printf("\n");
  14.                 return ;
  15.         }
  16.        
  17.         for(int j=1;j<=N;j++)
  18.         {
  19.                 if(!X[j])
  20.                 {
  21.                         q[i]=j;
  22.                         X[j]=true;
  23.                         dfs(i+1);
  24.                         X[j]=false;
  25.                 }
  26.         }
  27.        
  28.         return ;
  29. }
  30. int main()
  31. {
  32.         scanf("%d",&N);
  33.         dfs(0);
  34.        
  35.         return 0;
  36. }
复制代码
作者: lyc    时间: 2018-5-11 22:56

  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. int A[10],n;
  5. void dfs(int n,int *A,int js){
  6.      if(js == n){
  7.         for(int i=0; i<n; i++)
  8.         cout<<setw(5)<<A[i];
  9.      cout<<endl;
  10.      return;
  11.      }
  12.      else for(int i=1; i<=n; i++){
  13.      bool ok = 1;
  14.         for(int j=0; j<js; j++)
  15.            if(A[j] == i) ok = 0;
  16.         if(ok){
  17.               A[js] = i;
  18.               dfs(n, A, js+1);
  19.         }
  20.      }
  21. }
  22. int main(){
  23.     cin>>n;
  24.     dfs(n, A, 0);
  25.     return 0;
  26. }
复制代码

作者: diggersun    时间: 2018-5-11 23:22
lyc
作者: 吴语林    时间: 2018-5-12 11:56
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <map>
  6. #include <string>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. using namespace std;
  13. int a[20],book[20],n;
  14. void dfs(int cnt)
  15. {
  16.         if(cnt==n+1)
  17.         {
  18.                 for(int i=1;i<=n;i++)
  19.                         printf("%5d",a[i]);
  20.                 printf("\n");
  21.                 return;
  22.         }
  23.         for(int i=1;i<=n;i++)
  24.                 if(!book[i])
  25.                 {
  26.                         book[i]=1,a[cnt]=i;
  27.                         dfs(cnt+1);
  28.                         book[i]=0;
  29.                 }
  30. }
  31. int main()
  32. {  
  33.         scanf("%d",&n);
  34.         dfs(1);
  35.     return 0;
  36. }
复制代码
作者: 张笑宇    时间: 2018-5-13 17:26
  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. int n,a[10],b[10];
  5. void dfs(int x)
  6. {
  7.     if (x>=n+1)
  8.     {
  9.         for (int i=1; i<=n; i++)
  10.             cout<<setw(5)<<a[i];
  11.         cout<<endl;
  12.         return;
  13.     }
  14.     else
  15.     {
  16.         for (int i=1; i<=n; i++)
  17.         {
  18.             if (b[i]==false)
  19.             {
  20.                 b[i]=true;
  21.                 a[x]=i;
  22.                 dfs(x+1);
  23.                 b[i]=false;
  24.             }
  25.         }
  26.     }
  27. }
  28. int main()
  29. {
  30.     cin>>n;
  31.     dfs(1);
  32.     return 0;
  33. }
复制代码
作者: admin    时间: 2018-5-13 17:59
很好  基本的pmn 标准的算法
作者: 黄煦喆    时间: 2018-5-13 20:17
  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. int n,b[10],c[10],a[10]= {0,1,2,3,4,5,6,7,8,9};
  5. void ms(int i)
  6. {
  7.     if(i>n)
  8.     {
  9.         for(int j=1; j<i; j++)cout<<setw(5)<<c[j];
  10.         cout<<endl;
  11.     }
  12.     for(int k=1; k<=n; k++)
  13.         if(!b[k])
  14.         {
  15.             c[i]=a[k];
  16.             b[k]=1;
  17.             ms(i+1);
  18.             b[k]=0;
  19.         }
  20. }
  21. int main()
  22. {
  23.     cin>>n;
  24.     ms(1);
  25.     return 0;
  26. }
复制代码


diggersun: 你这个A[10] 是干什么用的？
作者: walk_alone    时间: 2018-5-13 21:22
  1. #include <cstdio>
  2. int a[10],n,book[10];
  3. void dfs(int step)
  4. {
  5.         if(step==n+1)
  6.         {
  7.                 for(int i=1;i<=n;i++)
  8.                         printf("%5d",a[i]);
  9.                 printf("\n");
  10.         }
  11.         else
  12.                 for(int i=1;i<=n;i++)
  13.                         if(book[i]==0)
  14.                         {
  15.                                 a[step]=i;
  16.                                 book[i]=1;
  17.                                 dfs(step+1);
  18.                                 book[i]=0;
  19.                                 a[step]=0;
  20.                         }
  21. }
  22. int main()
  23. {
  24.         scanf("%d",&n);
  25.         dfs(1);
  26.         return 0;
  27. }
复制代码

范彦廷提交
作者: liubo    时间: 2018-5-16 16:48
  1. #include<cstdio>
  2. const int maxn = 15;
  3. int n,c[maxn];
  4. void print(int cur){
  5.     if(cur == n){
  6.         for(int i = 0; i < n;i++)
  7.             printf("%5d",c[i]);
  8.         printf("\n");
  9.     }
  10.     else{
  11.         for(int i = 1;i <= n;i++){
  12.             int ok  = 1;
  13.             for(int j = 0;j < cur;j++){
  14.                 if(i == c[j]){ok = 0;break;}
  15.             }
  16.             if(ok){c[cur] = i;print(cur+1);}
  17.         }
  18.     }
  19. }
  20. int main(){
  21.     scanf("%d",&n);
  22.     print(0);
  23.     return 0;
  24. }

复制代码


注意精简自己的程序
作者: YTC    时间: 2018-5-21 12:52
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
int a[10],n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=i;
    do
    {
        for(int i=1;i<=n;i++) cout<<setw(5)<<a[i]; cout<<endl;
    }while(next_permutation(a+1,a+1+n));
    return 0;
}
作者: Scorpio    时间: 2018-6-9 15:05
  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. int a[105],b[105];
  5. int n;
  6. void hhh(int i)
  7. {
  8.     int j,k;
  9.     if(i>=n+1)
  10.     {
  11.         for(j=1;j<=n;j++)
  12.             cout<<setw(5)<<a[j];
  13.         cout<<endl;
  14.         return;
  15.     }
  16.     else for(k=1;k<=n;k++)
  17.     {
  18.         if(b[k]==0)
  19.         {
  20.             a[i]=k;
  21.             b[k]=1;
  22.             hhh(i+1);
  23.             b[k]=0;
  24.         }
  25.     }
  26. }
  27. int main()
  28. {
  29.     cin>>n;
  30.     hhh(1);
  31.     return 0;
  32. }
复制代码
作者: lwy    时间: 2018-6-12 16:47
#include<iostream>
#include<iomanip>
using namespace std;
int a[11];
bool vis[11];
int n;
void dfs(int plc)
{
    if(plc>n)
    {
        for(int i=1;i<=n;i++)
            cout<<setw(5)<<a[i];
        cout<<endl;

        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            vis[i]=1;
            a[plc]=i;
            dfs(plc+1);
            vis[i]=0;
        }
    }


}

int main()
{
    cin>>n;
    dfs(1);
    return 0;
}
作者: Duoluo    时间: 2018-6-16 16:06
  1. #include <iostream>
  2. using namespace std;
  3. int n;
  4. bool x[10];
  5. int a[10];
  6. void  dfs(int i)
  7. {
  8.   
  9.     if(i==n)
  10.     {
  11.         for(int q=0;q<n;q++) cout<<a[q]<<" "; cout<<endl;
  12.     }
  13.     else
  14.     {
  15.         for(int j=1;j<=n;j++)   
  16.         {
  17.             if(x[j])
  18.             {
  19.                 a[i]=j;
  20.                 x[j]=false;
  21.                 dfs(i+1);
  22.                 x[j]=true;
  23.             }
  24.         }
  25.     }
  26. }
  27. int main()
  28. {
  29.     cin>>n;
  30.     for(int ans=1;ans<=n;ans++)
  31.     x[ans]=1;
  32.     dfs(0);
  33.     return 0;
  34. }
复制代码
作者: 倚窗倾听风吹雨    时间: 2018-7-12 13:52
  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. int n,a[10];
  5. bool b[10];
  6. void dfs(int x)
  7. {
  8.     int i;
  9.     if(x==n+1)
  10.     {
  11.         for(i=1; i<=n; i++)
  12.             cout<<setw(5)<<a[i];
  13.         cout<<endl;
  14.         return;
  15.     }
  16.     else
  17.         for(i=1; i<=n; i++)
  18.         {
  19.             if(!b[i])
  20.             {
  21.                 b[i]=true;
  22.                 a[x]=i;
  23.                 dfs(x+1);
  24.                 b[i]=false;
  25.             }

  27.         }
  28. }
  29. int main()
  30. {
  31.     cin>>n;
  32.     dfs(1);
  33.     return 0;
  34. }
复制代码
作者: universehyf    时间: 2018-9-1 22:17
特别无聊地上STL algorithm 中的神奇函数
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int main(){
  5.     int n,p[10],i;
  6.     cin>>n;
  7.     for(i=0;i<n;i++) p[i]=i;
  8.     do{
  9.         for(i=0;i<n;i++) cout<<p[i]<<" ";
  10.         cout<<endl;
  11.     }while(next_permutation(p,p+n));  //求下一个排列
  12.     return 0;
  13. }
复制代码
作者: ZMQ    时间: 2018-9-4 17:02
提示: 作者被禁止或删除 内容自动屏蔽
作者: 朱品屹    时间: 2020-8-5 10:08
  1. #include<iostream>
  2. using namespace std;
  3. int a[11]={0,1,2,3,4,5,6,7,8,9},n;
  4. bool b[11]={0,1,1,1,1,1,1,1,1,1};
  5. void pr()
  6. {
  7.         for(int i=1;i<=n;i++) cout<<"    "<<a[i];
  8.         cout<<endl;
  9. }
  10. void pmn(int i)
  11. {
  12.         if(i>n) pr();
  13.         else
  14.         {
  15.                 for(int k=1;k<=n;k++)
  16.                 {
  17.                         if(b[k]==1)
  18.                         {
  19.                                 a[i]=k;
  20.                                 b[k]=0;
  21.                                 pmn(i+1);
  22.                                 b[k]=1;
  23.                         }
  24.                 }
  25.         }
  26. }
  27. int main()
  28. {
  29.         cin>>n;
  30.         pmn(1);
  31.         return 0;
  32. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2