递归思想

实质：一种思考问题的方法（不局限于一类具体的算法）

递归的两个重要概念：——代码实现的关键点

递归边界（分解的尽头）

递归式 （分解的手段）

分治算法理解

地位：递归思想的经典实现

分治法三步骤：
1划分：将原问题分解为若干和原问题具有相同或相似结构的子问题

2求解：递归求解所有子问题

3合并：将子问题的解合并为原问题的解

强调：分治法分解出的子问题应当是相互独立，没有交叉的

如果两个子问题有交互部分，则不应当使用分治法解决

分治算法的经典实现

01全排列问题

问题描述：实现对n个数的全排列

解题思路：

分治：n个数的全排列、n-1个数的全排列、……1个数的全排列

每一层以1开头的全排列、以2开头的全排列、……以n开头的全排列

细节：每一层中注意状态还原（横向思考）

已完成排列的数的flag标记（纵向思考）

共同点：对可行解的实时存储

敲黑板的强调：对可行解的循环必须利用maxn限制，而非n进行限制（其中的易错之处自己领会）

代码实现：

 1 #include<cstdio> 2  3 int flag[100]={0}; 4 int tempStore[100]; 
 5  6 const int maxn=3; 7 int count=0; 8  9 void fullPermutation(int n)10 {11     if(n==0) 
12     {13         for(int i=1;i<=maxn;i++)14         printf("%d ",tempStore[i]);15         printf("\n");16         return;17     }18     19     for(int i=1;i<=maxn;i++)20     {21         if(flag[i]==0) 
22         {23             count++;24             tempStore[count]=i;25             flag[i]=1;26             fullPermutation(n-1);27             flag[i]=0;28             count--;29         }30     }31 }32 33 int main()34 {35     int n=maxn;36     fullPermutation(n);37     return 0;38 }

02N皇后问题

问题描述：在一个N*N的棋盘上放置N个皇后，使得皇后两两不在同一行，同一列，同一条对角线上

解题思路：

分治：由行的增加进行纵向思考，由列的筛选进行横向思考

难点：同一条对角线的判断——行列之差的绝对值是否相等

共同点：对可行解的实时存储

代码实现：

 1 #include<cstdio> 2 #include<cstdlib> 3  4 const int N=8; 5  6 int a[N+1][N+1]={0};    
 7  8 int C[N+1];        
 9 int ans=0;      
10 11 void search(int cur)      
12 {13     if(cur==N+1)     
14     {15         ans++; 
16         return ;17     } 
18         19     for(int j=1;j<=N;j++)20     {21         int flag=1;     
22         C[cur]=j;23         24         for(int i=1;i<cur;i++)        
25         if( C[cur]==C[i] || ( abs(cur-i)== abs(C[cur]-C[i]) ) )    
26         {27             flag=0;28             break;29         }30         31         if(flag==1)            
32         {33             a[cur][C[cur]]=1;34             search(cur+1);     
35             a[cur][C[cur]]=0;     
36         }        
37     }38 39 }40 41 int main()42 {43     search(1);44     printf("%d",ans); 
45     return 0; 
46 }