欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

递归思想

程序员文章站 2022-06-01 19:08:04
递归思想 实质:一种思考问题的方法(不局限于一类具体的算法) 递归的两个重要概念:——代码实现的关键点 递归边界(分解的尽头) 递归式 (分解的手段) 分治算法理解 地位:递归思想的经典实现 分治法三步骤: 1划分:将原问题分解为若干和原问题具有相同或相似结构的子问题 2求解:递归求解所有子问题 3 ......

递归思想

实质:一种思考问题的方法(不局限于一类具体的算法)

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

递归边界(分解的尽头)

递归式    (分解的手段)

 

分治算法理解

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

分治法三步骤:
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并跳出