全排列(dfs、递归)通俗易懂
dfs算法在蓝桥杯是高频考点，下面是我写的第一个dfs题目，是基本的dfs模板题，但是我想了很久才搞明白。是这样想通的，首先了解数据结构和dfs算法的基本思路是怎么样的（学过数据结构理解就很简单），套框架，按照步骤思考每一步应该是怎么样，之后思考程序每一步走到哪（关键），用意是什么，走出两三组数就豁然开朗了。可以在草稿上写下流程图，使思路更清醒哦。解题思路在代码中注明了很详细，耐心想想其实很简单，不清楚的地方欢迎评论区留言。
#include<stdio.h>//uncle-lu
//对当前的位置进行深度优先搜索，找到每个可以填进去的数进行尝试。搜完了这个位置以后回溯继续搜。
int n;
int line[10];
bool visit[10];
void print()
{for(int i=1; i<=n; ++i)printf("%d ", line[i]);printf("\n");return ;
}
void dfs(int x) //每组的第x个数
{if(x>n)print();//objective 4一共n个数都搜完了我们应该干啥？for(int i=1; i<=n; ++i){if(visit[i]);//objective 1 如果这个数用过了怎么办？下一个循环使用下一个数else{//objective 2如果没用过要搜索这个数，需要处理哪些东西？为了不重复我们应该如何利用visit数组标记？line[x]=i; //第x个数赋值为i;visit[i]=1; //i这个数值已访问dfs(x+1); //递归调用visit[i]=0;//不使用数值i了}}return;
}
int main()
{scanf("%d",&n);dfs(1);//objective 3我们应该先搜哪里？明显是1return 0;
}
如果本文对您有帮助，可不可以给萌新点一个赞，鼓励小萌新坚持写博客的热情！
全排列(dfs、递归)通俗易懂
dfs算法在蓝桥杯是高频考点，下面是我写的第一个dfs题目，是基本的dfs模板题，但是我想了很久才搞明白。是这样想通的，首先了解数据结构和dfs算法的基本思路是怎么样的（学过数据结构理解就很简单），套框架，按照步骤思考每一步应该是怎么样，之后思考程序每一步走到哪（关键），用意是什么，走出两三组数就豁然开朗了。可以在草稿上写下流程图，使思路更清醒哦。解题思路在代码中注明了很详细，耐心想想其实很简单，不清楚的地方欢迎评论区留言。
#include<stdio.h>//uncle-lu
//对当前的位置进行深度优先搜索，找到每个可以填进去的数进行尝试。搜完了这个位置以后回溯继续搜。
int n;
int line[10];
bool visit[10];
void print()
{for(int i=1; i<=n; ++i)printf("%d ", line[i]);printf("\n");return ;
}
void dfs(int x) //每组的第x个数
{if(x>n)print();//objective 4一共n个数都搜完了我们应该干啥？for(int i=1; i<=n; ++i){if(visit[i]);//objective 1 如果这个数用过了怎么办？下一个循环使用下一个数else{//objective 2如果没用过要搜索这个数，需要处理哪些东西？为了不重复我们应该如何利用visit数组标记？line[x]=i; //第x个数赋值为i;visit[i]=1; //i这个数值已访问dfs(x+1); //递归调用visit[i]=0;//不使用数值i了}}return;
}
int main()
{scanf("%d",&n);dfs(1);//objective 3我们应该先搜哪里？明显是1return 0;
}
如果本文对您有帮助，可不可以给萌新点一个赞，鼓励小萌新坚持写博客的热情！
发布评论