欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

简单的全排列问题(给初学者)

程序员文章站 2022-06-24 12:53:59
洛谷P1706 全排列问题 题目描述 输出自然数1到n所有不重复的排列,即n的全排列,要求所产生的任一数字序列中不允许出现重复的数字。 输入输出格式 输入格式: n(1≤n≤9) 输出格式: 由1~n组成的所有不重复的数字序列,每行一个序列。每个数字保留5个常宽。 输入输出样例 输入样例#1: 3 ......

洛谷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
深搜;print为输出函数,%5d就是题目要求 每个数字占五个长宽,dfs深搜,if(!a[i])是如果它等于0的意思,dfs(x+1)后面的a[i]=0为回溯,
执行这个的条件是当for循环完了还不满足if(x==n)是,就执行这一句回溯,(可以自己调试看看),回溯后返回上一层,
也就是x,回溯前是x+1,回溯后是x,可以理解为x+1-1,-1就代表回溯到上一步,然后main函数里的dfs(0),为什么是0?
对于dfs,可以先0,先1,先x……都可以,根据自己的代码来,这里从零开始,跳到dfs函数,那么x就等于0,然后紧接着x+1就等于1,b[x+1]=i;
也就是b[1]=i是刚好的,如果dfs(1),那x+1就等于2,那就错了。嗯,,,一开始我也很绝望,,真的看不懂,现在好像也还有点儿,,,我把我
难理解的写出来了,仅仅是给新手看的,有什么问题可以问我,我帮你们问比我更厉害更厉害的人哈哈哈哈哈。邮箱:2412730666@qq.com


#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,b[11];
bool a[233];
void print()
{
  for(int i=1;i<=n;i++)
    printf("%5d",b[i]);
  cout<<endl;
}
void dfs(int x)
{
  int i;
  if(x==n)
  {
    print();
    return ;
  }
  for(int i=1;i<=n;i++)
  {
    if(!a[i])
    {
      a[i]=1;
      b[x+1]=i;
      dfs(x+1);
      a[i]=0;
    }
  }
}
int main()
{
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
    b[i]=i;
  dfs(0);

  return 0;

}