n-皇后以及全排列的问题--递归以及非递归的解法

首先说下全排序的问题  这个问题可以说是最经典的问题，

 

实现这个问题的最经典的方法莫过于递归实现了：

 

代码确实很简洁：（从网上转载---很多的）

void perm(char *buf,int start,int end)
 {   
        if(start==end){//当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可    
            for(int i=0;i<=end;i++){   
                printf("%c",buf[i]);   
            }   
            printf("\n");      
        }   
        else{//多个字母全排列    
            for(int i=start;i<=end;i++){   
                char temp=buf[start];//交换数组第一个元素与后续的元素    
                buf[start]=buf[i];   
                buf[i]=temp;   
                   
                perm(buf,start+1,end);//后续元素递归全排列    
                   
                temp=buf[start];//将交换后的数组还原    
                buf[start]=buf[i];   
                buf[i]=temp;   
            }   
        }   
    }   

 简介带来的问题就是递归算法本身就不是很容易理解，另外一方面就是递归算法比较浪费内存空间。

 

  首先就是perm(buf【】,start,end)实现数组的start的索引到end索引的全排序，每次我们需要从第一个元素与需要全排的索引的第一个交换，求解完后在替换回来。。。如此递归下去，只能说到这里了，再说下去我也很迷糊

这种递归算法也有缺点，就是它不能取出中间重复的序列，加入求1,2,2,3的全排列不能取出重复的  需要另外的便利控制。。。

 

在网上看到一些全排序比较新颖的实现方法---字典序列的方法来就全排序

比如求3,1,2,4的全排列，

这种方法将这些序列进行了一个排序，比如得到全排序之后的的所有序列第一个序列是，1,2,3,4 最后一个序列是4,3,2,1

也就是递增的方法来查找序列，比如，3214的下一个序列就是3241

 

问题的关键就是如何调整这个数的 序列

方法如下：

1. 首先对要求全排序的数列进行递增的排序，

2.从序列的最后端点开始查找这样的一个元素，这个元素比相邻的后面的元素小，记录下这个元素的下标i;

3.然后此时i后方的元素是整体递减的，所以我们直接从序列的最后方开始找比元素大的元素，并记录下标j；

4，然后swap（A[i]，A[j]）；

5，将元素i后方的所有元素逆转；

6.然后输出，新的序列

7.知道序列全部递减停止；

 

void swap(int *a,int *b) //交换
{
	int tmp=*a;
	*a=*b;
	*b=tmp;
}

void revArr(int *arr,int k,int m) //数组arr 从k到m进行逆置
{
	while(k<m)
	{
		swap(arr+k,arr+m);
		k++;
		m--;
	}
}

void print(int *x,int n)   //打印
{
		for(int i=0;i<n;i++)
				{
 	               printf("%d ",x[i]);
				}
				printf("\n"); 
}

int fullArr(int *arr,int n)
{
	if(n==1)
	{
		return 1;
	}
	int i,j;
	while(1)
	{
        print(arr,n);

		for(i=n-2;i>=0;i--)       
		{
			if(arr[i]<arr[i+1])  //从数组后方找到后一个数大于前一个数  记住下表i
			{
				break;
			}
			if(i==0)
			{
				return 1;//函数结束出口
			}
		}

		for(j=n-1;j>i;j--)   //在i后方找到一个数比i大而且最接近i的数，我们可以直接从后先前找，因为i后方的数都是升序的
		{
			if(arr[j]>arr[i])
			{
				break;
			}
		}
		swap(arr+i,arr+j);    //交换i与j
        revArr(arr,i+1,n-1);   //i后方的数逆置
	}
}

 

说到递归 不得不让人想起n-皇后问题。

 

问题描述，就是在一个n*n的棋盘上防止n个棋子，其中任何两个棋子不可以在同行，同列，同一斜线上出现。

 

解决这个问题的最经典思路就是回溯法：

在解空间内（树），根据剪枝函数（约束函数）来去除不合适的解路径（采用深度优先遍历的方式来遍历接空间树），找到合适的解路径；

 

首先定义一个长度为n的数组blank，初始化全为-1，每个元素代表第i行上防止棋子的列数。

 

剪枝函数的条件：if(x[j]==i||abs(x[j]-i)==abs(j-k)) return false；

 

从树第第一层开始，逐个向下查找，加入到k层，查找失败则返回带k-1层，继续查找。。直到最后blank[n-1]==n  退出并返回

下面是非递归的实现--容易理解

 

void BackTrack(int *blank,int n)// n-皇后的非递归实现
{
	 for(int i=0;i<n;i++)  //初始化n-元组--
	 {
		 blank[i]=0;
	 }

	 int k=0;
	 while(blank[0]!=n)  //当遍历到最后时，blank[0] 会自加到n
	 {
		 while(blank[k]<n&&!place(k,blank[k],blank))  //首先找到复合条件的点
		 {
			 blank[k]++;
		 }

		 if(blank[k]<=n-1)                     
		 {
		     if(k==n-1)   //遍历到最后一层  成功
			 {
		 	 //成功
				 for(int j=0;j<n;j++)
				 {
 	               printf("%d ",blank[j]);
				 }
				 printf("\n"); 
				 blank[k]++;
			 }
	    	 else   //检查到下一个节点
			 {
		    	 k++;
		    	 blank[k]=0;
			 }
		 }
		 else
		 {
			 k--;
			 blank[k]++;
		 }
	 }
}