递归思想

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

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

递归边界（分解的尽头）

递归式    （分解的手段）

 

分治算法理解

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

分治法三步骤：
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 }

 

 

 

 

针对可行解进一步纵向深入的思考：

两个方向：（方向的选择依据题目条件进行判断）

• 判断当前解是可行的吗
• 判断当前解是不可行的吗（更具有普适性）

核心：flag标志变量（每一次当前解筛选的最开始处之前置1）

           一旦明确当前解不可行，则置0并跳出