蓝桥杯算法竞赛系列第二章——深入理解重难点之递归（下）
欢迎回到：遇见蓝桥遇见你，不负代码不负卿！
【前言】：铁汁们在看这篇文章之前，先将递归上半部分大致看一下，再次加深认识。
https://blog.csdn.net/weixin_57544072/article/details/120836167utm_source=app&app_version=4.16.0
目录
一、精选题讲解
1、斐波那契数列
题目描述：求斐波那契数列的第N项，1 1 2 3 5 8 13 21...
三段论
找重复：求前两项是原问题的重复，规模更小，是其子问题
找变化：很明显，只有n在变化
找边界：当n == 1 || n == 2时结束
代码执行
-
#include<stdio.h>
-
-
int fac(int n)
-
{
-
//找边界
-
if (n == 1 || n == 2)
-
{
-
return 1;
-
}
-
//找重复
-
return fac(n - 1) + fac(n - 2);
-
}
-
-
int main()
-
{
-
int ret = fac(7);
-
-
printf("%d\n", ret);
-
-
return 0;
-
}
这里笔者要补充另外一种递归解题思维，所以请铁汁们先回顾一下，看看笔者在递归上篇讲了什么
https://blog.csdn.net/weixin_57544072/article/details/120836167utm_source=app&app_version=4.16.0
我在递归（上）里面讲到一种“切蛋糕思维”式的解题方法，它能够解决很多平常我们遇到的递归类的题目，但是就本题而言，单单是“切一刀”是解决不了问题的
求斐波那契数列的第N项，即求f(N), 这里如果只是“划一刀”，则变成了f(N - 1),很显然，只划一刀是解决不了本题的，但是不难看出，f(N) = f(N - 1) + f(N - 2),也就可以理解为上篇中提到的把蛋糕比作“项目”，在上一篇中，小高这个人比较懒，他呢，只做了一丢丢，剩下的很大一部分都委派给了另外一个人用递归的方式去完成。 但是在这里，他更懒了，懒到那一丢丢都不想做，直接全权委派给了另外两个人用递归的方式去解决。
所以：上篇博文都是"划一刀“就解决问题了，现在可就不行了噢，所以铁汁们，当你们以后遇到递归的题目，先看看”划一刀”能不能解决，不能解决时也别忙转换思路，先看看自己是不是形参写少了，实在没找出毛病，再想想是不是需要转化思维。
总结：上一篇博文都是利用“切蛋糕思维” ，f (N) = x + f(N + 1)
其存在变体是：f(N) = f(N / 2) + f(N / 2)-->两次规模凑起来是一个规模，后面可能遇到。
而今天博文中提到的斐波那契数列比较特殊：f(N) = f(N - 1) + f(N - 2)
所以：递归可以分解为：直接量 + 小规模子问题；也可以分解为：多个小规模子问题
其实在实际运用当中，我们不会采用递归的方式去求斐波那契数列，因为它进行了大量的重复运算，至于为什么，后面讲到二叉树的时候会详细介绍，这里就不过多赘述了。
所以为了避免进行大量多余的计算，我们会选用迭代去求斐波那契数列问题，也就是常说的循环。
-
#include<stdio.h>
-
int fib(int n)
-
{
-
int last2 = 1;
-
int last1 = 1;
-
int cur = 1;
-
for (int i = 3; i <= n; i++)
-
{
-
cur = last1 + last2;
-
last2 = last1;
-
last1 = cur;
-
}
-
return cur;
-
}
-
int main()
-
{
-
printf("%d\n", fib(7));
-
return 0;
-
}
2、青蛙跳台阶
题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上两级，求：该青蛙跳上一个n级的台阶总共有多少种跳法？
注意：注意这个题目问的是什么？
问的不是青蛙能跳多少次，而是有多少种跳法能到最后一个台阶。
问题分析：当n > 2时，第一次跳就有两种不同的选择：一是第一次只跳一级，此时跳法数目等于后面剩下的（n - 1）级台阶的跳法数目，即为f(n - 1); 还有一种选择是第一次跳两级，此时跳法数目等于后面剩下的（n - 2）级台阶的跳法数目，即为f(n - 2).
所以有：f(n) = f(n - 1) + f(n - 2)
当n == 1时，有1种跳法；
当n == 2时，有2种跳法；
当n == 3时，有3种跳法；
当n == 4时，有5种跳法。
是呀，这题跟斐波那契数列基本上一样，不过这道题目需要思考一下，没有斐波那契这么明显。
三段论
找重复：求（n - 1）和（n - 2）个台阶的跳法，是原问题的重复，规模更小，是其子问题
找变化：很显然，n一直在变化
找边界:当n == 1时或者n == 2时，就找到出口了
代码执行
-
#include<stdio.h>
-
int jumpfloor(int n)
-
{
-
//找边界
-
if (n == 1)
-
{
-
return 1;
-
}
-
if (n == 2)
-
{
-
return 2;
-
}
-
//找重复
-
return jumpfloor(n - 1) + jumpfloor(n - 2);
-
}
-
-
int main()
-
{
-
printf("%d\n", jumpfloor(5));
-
return 0;
-
}
3、最大公约数
辗转相除法
可能我们求最大公约数的时候多采用“辗转相除法” ，其实也可以采用递归的方式去求最大公约数。首先补充辗转相除法求最大公约数：
代码执行
-
#include<stdio.h>
-
-
int main()
-
{
-
int m = 24;
-
int n = 18;
-
int r = m % n;
-
while (r != 0)
-
{
-
r = m % n;
-
m = n;
-
n = r;
-
}
-
-
printf("最大公约数为：%d\n", m);
-
-
return 0;
-
}
递归代码
-
#include<stdio.h>
-
-
int gcd(int m, int n)
-
{
-
if (n == 0)
-
{
-
return m;
-
}
-
return gcd(n, m % n);
-
}
-
-
int main()
-
{
-
printf("%d\n",gcd(24,42));
-
return 0;
-
}
所以：当“切蛋糕思维”解决不了问题时，想想有没有递归公式，有没有等价转换。看看能不能将范围缩小，这都是需要经过大量训练才能掌握的规律，加油加油，看完笔者的博文，要把里面的题目全都掌握哦，都是基础题，之后再去牛客网，力扣里面刷题，听的再多都不如自己用代码实现出来！
4、汉诺塔问题
题目描述：汉诺塔问题是一个很经典的问题，有三根柱子，在一根柱子上，从下往上按照大小顺序摞着64个圆盘，现需要将圆盘全部摆放到另一根柱子上去，并且规定，任何时候，在小圆盘上面都不能放大圆盘，也就是始终要保证大盘在底下，小盘在上面。
解题思路
将A柱上面的4个圆盘放到C柱上，可以先通过B、C将4个盘子上面的3个移动到B上去，然后将大盘放到C上，最后通过A、B重复操作将那3个盘子放到C上。
代码执行
-
public class Recursion {
-
-
//从pos1位置移动到pos2位置
-
public static void move(char pos1, char pos2) {
-
System.out.print(pos1 + "->" + pos2 + " ");
-
}
-
//形参分别代表盘子个数、起始位置、中途位置、目的地位置
-
public static void hanoi(int n, char pos1, char pos2, char pos3) {
-
//终止条件
-
if(n == 1) {
-
move(pos1, pos3);
-
return;
-
}
-
//先将(n - 1)个盘子通过B、C移动到B上去
-
hanoi(n - 1, pos1, pos3, pos2);
-
//再将大盘放到C上
-
move(pos1,pos3);
-
//再将B柱上的盘子通过A、C放到C上
-
hanoi(n - 1, pos2,pos1,pos3);
-
}
-
public static void main(String[] args) {
-
-
hanoi(4,'A','B','C');
-
}
-
}
注意事项：一定不要想着去展开代码，做递归题目要学着横向思考。还是那句话，多做，多练，多敲。这道题目为了让大家理解怎么拿，怎么放，所以就没有真正去实现，否则还会用到后面一个模块的知识，在后面的博文中会做详细介绍。
二、思考题：放苹果
题目描述：把m个相同的苹果放到n个相同的盘子里，允许有的盘子空着不放，问可以有多少种不同的方法？注意：5 1 1 和 1 5 1是同一种分法
由于这道题目对于没有遇到过的铁汁们可能有点绕，所以我先将大致思路说一下，注意哦，解开本题的话一定要留意今天主要讲的是什么哦。
大致思路：设i个苹果放在k个盘子里的放法总数是：f(i, k), 则：
1、当k > i时，说明盘子比苹果要多，必然有盘子是空的（k - i）个，所以将（k - i）个盘子放在一边不用，剩下的问题就变成了将i个苹果放到i个盘子里
2、当k <= i时，将放法分为有盘子为空和无盘子为空两类，所以它的总放法 = 有盘子为空的方法 + 没盘子为空的放法
好咯，铁汁们，大致思路就说这么多哦，要尝试着自己做出来哦，等到该系列的下一篇博文发出，笔者会详细讲解的。
三、蓝桥结语：遇见代码遇见你，不负代码不负卿
说到这里，蓝桥杯算法竞赛系列第二章递归基础知识部分结束了，哈哈，没错，后面还有的，等到笔者把剩下的几个基础算法的基础知识部分讲完之后，还会附加大量的练习，以及历年的蓝桥真题，递归这么重要当然跑不掉，正好那个时候顺便再复习这里的基础知识。
说到这里，请铁汁们，再将递归这两篇博文好好看一遍，冲冲冲。
https://blog.csdn.net/weixin_57544072/article/details/120836167?utm_source=app&app_version=4.16.0
又到结尾咯，笔者再次请求铁汁们如果觉得有所收获的话，给笔者来个一键三连，捧个人场就行了哈，你们的支持就是笔者最大的动力哦。蟹蟹铁汁们。
文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。
原文链接：bit-runout.blog.csdn.net/article/details/120917038
- 点赞
- 收藏
- 关注作者
评论（0）