递归思想
程序员文章站
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并跳出
上一篇: rabbitmq实现向各服务广播消息
下一篇: Java面向对象(中)