简单的全排列问题(给初学者)
程序员文章站
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;
}
下一篇: fastRPC服务使用
推荐阅读
-
js实现字符全排列算法的简单方法
-
DFS中关于全排列、组合、子集中有重复数字去重的问题
-
【康托展开】全排列中某一排列的字典序计算问题
-
简单的全排列问题(给初学者)
-
初学者问个简单的逻辑有关问题,求解答
-
初学者问个简单的逻辑有关问题,求解答
-
【请问我用DW8给网页做好了布局,在CS5打开布局怎么全乱了,预览的时候又没问题?怎么解决?】_html/css_WEB-ITnose
-
mysql存储过程,使用的navicat,给变量赋值的简单问题
-
【请问我用DW8给网页做好了布局,在CS5打开布局怎么全乱了,预览的时候又没问题?怎么解决?】_html/css_WEB-ITnose
-
java面试第一次问题,时间没把握好,有点紧张,其实都是很简单的题,笔试感觉良好,面试可能回答不太满意,继续加油,建议初学者把基础学扎实,葵花宝典你值得拥有