[啊哈算法]数的全排列_C

先来看题：

本题是一个经典的dfs问题，在n固定的情况下可以用几层循环解决问题，而题目中n不固定，所以要用搜索的方式解决问题。

全排列的问题是最经典的dfs问题，所以本题考的主要是dfs（class="superseo">深度优先搜索）的思维。

简单介绍一下dfs算法：一直往深处走，直到找到解或者走不下去为止，好比遇到一个分岔口，先随便选一条路走，例如选择了左边的路，无论结果如何都要返回这个岔路口，试探右边的路。这其中涉及到一个“回溯”的思想，即“回到岔路口”这一行为，所以我们需要用到函数的递归调用。

下面先来看代码：

#include
int n;
int a[20],book[20]={0};
void dfs(int step)
{
	if(step==n)//当放入足够的数字之后，输出 
	{
		for(int i=0;i

 
下面我来模拟一下这个流程： 
首先进入主函数，接收一个n，这个n即为排列数的总数，同时也是一组数中的最大数。我们假设n=3； 
step可以理解为“步数”，每走一步，相当于往排列中填进一个数字，n=3的情况下，我们一共需要走三步，在一开始调用dfs函数时，我们还一步没有走，所以dfs(0)； 
进入dfs函数后，我们先要想好出函数，也就是回溯的条件，当我们step==3时，我们已经填入了三个数，输出他们，并return。注意每次进入函数后，先要判断是否满足出函数的条件。 
接下来就是函数的主体部分 
当n=3时，我们可以选择在一个排列中的第一个数的位置放入“1，2，3”中任意一个数字，在这里我们规定了一个循环来从小到大遍历每一位数字。 
进入循环后可以发现我们利用了两个不同含义的数组 
a数组是我们储存排列用的数组，也就是我们需要往a的1~3填入数字； 
而book数组是一个供我们进行判断的数组，因为全排列中，每个数字只能使用一次，可以理解为有三张卡片，卡片上分别标有1，2，3三个数字，一开始三个卡片都没有被使用过，我们规定book中的数字都为0，而只有book值为0的数才会被我们考虑填入a中，当1被使用后，我们让book[1]=1，标记为使用，下次再调用函数时就不会考虑1这个数字。 
当我们发现一个合理的数字后，我们将他填入数组a中，同时令step加一，并再次进行调用dfs，考虑下一个数字。 
最后是book[j]=0，即让这个数接触标记，因为他是调用完dfs的后一步，这个数字已经参与完排列并输出了，我们需要进行还原，来使这个数字之后也可以被调用。 
 
 这是我用画图模拟的流程 
对于2，3的模拟我就省略了，和1类似。 
总结：全排列问题是一个很经典的dfs问题，对于初学者来说，递归调用是比较难理解的，比如还有一个汉诺塔问题也有异曲同工之妙（在考虑要不要写个汉诺塔呢），总之还是要多看题好好理解啊qwq~；					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/716832.html

[啊哈算法]数的全排列

发表评论

评论列表（0条）