[置顶] 深度优先搜索与全排列
发布时间：2020-12-13 20:45:46 所属栏目：PHP教程 来源：网络整理
导读：做题进程中我们常常会遇到这样的问题： 输入1个数n,输出1-n的全排列。可能很多人会想到枚举暴力，这里给大家介绍1种算法： 深度优先搜索 在这里举个简单的例子 假设有编号为1 、2、3 的3 张扑克牌和编号为l 、2 、3 的3 个盒子。 现在需要将这3 张扑克牌分别
|
做题进程中我们常常会遇到这样的问题： 输入1个数n,输出1-n的全排列。可能很多人会想到枚举暴力，这里给大家介绍1种算法：深度优先搜索 在这里举个简单的例子 假设有编号为1 、2、3 的3 张扑克牌和编号为l 、2 、3 的3 个盒子。 首先 我们应当设置1个标志数组 book 记录当前数字是不是被使用过。 然后用1个数组a 表示盒子并且初始化a[i]=i;
代码以下： #include<stdio.h>
int n,a[10],book[10];//特别说明c语言全局变量没有赋值默许为 0,无需再次初始化；
void dfs(int step)//step 表示当前在第几个位置
{
int i;
if(step==n+1)//如果step==n+1表示前n个数字已放好
{
//输出1种全排列
for(i=1;i<=n;i++)
printf("%d",a[i]);
printf("
");
return;
}
//每次搜索都从1-n 逐一尝试
for(i=1;i<=n;i++)
{
if(book[i]==0)//判断次数字是不是用过
{
a[step]=i;//存储当前位置的数字，以便满足条件输出
book[i]=1;//当前数字已用过，改变标志，以防重用
dfs(step+1);//放好当前位置数字以后，安排下1个数字
book[i]=0;//回溯，当满足1种全排列后，进行下1种尝试
}
}
return ;
}
int main()
{
scanf("%d",&n);//输入只能为1⑼之间的整数，表示1-n的全排列
dfs(1);//从第1个位置开始
return 0;
} 同时总结了下基本模型，希望有用： void dfs(int step)
{
判断边界
尝试每种可能
for(i=1;i<=n;i++)
{
继续下1步dfs(step+1);
}
返回
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |