【数据结构算法(一)】递归篇(常见实例讲解)

🌈键盘敲烂,年薪30万🌈

本篇讲解实例:

  • 斐波那契、兔子问题、猴子吃桃问题、跳台阶问题、汉诺塔、杨辉三角

用到的递归思想:

  • 无记忆递归、记忆递归(重点掌握)

目录

一、斐波那契:

①无记忆多路递归:

②⭐记忆递归:

二、兔子问题:

三、跳台阶问题:

四、汉诺塔问题:

五:杨辉三角问题:

①无记忆递归:

②⭐记忆递归:

六、猴子吃桃问题:


一、斐波那契:

问题描述:

这个数列的每个数字都是前两个数字之和,数列的第一个和第二个数规定为1

①无记忆多路递归:
  • 时间复杂度:O(n^2) -  很恐怖
public class FibonaciNoMemory {// 1 1 2 3 5 8 13 21 34 55……public static void main(String[] args) {int n = 10;//无记忆性的递归int ans2 = noMemoryRecursion(n);System.out.println(ans2);}private static int noMemoryRecursion(int n) {if(n == 1 || n == 2){return 1;}return noMemoryRecursion(n-1) + noMemoryRecursion(n-2);}
}
②⭐记忆递归:
  • 时间复杂度:O(n)
public class FibonaciRemind {public static void main(String[] args) {int n = 10;int ans = remindRecursion(n);System.out.println(ans);}private static int remindRecursion(int n) {int[] cache = new int[n+1];Arrays.fill(cache, -1);cache[0] = 1; cache[1] = 1;return help(n-1, cache);}private static int help(int n, int[] cache) {if(cache[n] != -1){return cache[n];}int val = help(n-1, cache) + help(n-2, cache);cache[n] = val;return val;}
}

 

二、兔子问题:

问题描述:

有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?

代码同斐波那契差不多,多了个求和,这个兔子问题就是列昂纳多·斐波那契引申出的。

public class a06_rabbit {public static void main(String[] args) {int month = 10;int count = getCount(month);System.out.printf("第十个月,共%d只兔子", count);}private static int getCount(int month) {int[] cache = new int[month];cache[0] =  1;cache[1] = 1;help(month-1, cache);int total = 1;for (int i = 0; i < month; i++) {total += cache[i];}return total;}private static int help(int month, int[] cache) {if(cache[month] != 0){return cache[month];}cache[month] = help(month - 1, cache) + help(month - 2, cache);return cache[month];}
}

 

三、跳台阶问题:

问题描述:

鸡哥跳台阶,有时跳一阶,有时跳二阶,问,若有10层台阶,有多少种跳法

public class SkipStairs {public static void main(String[] args) {int n = 10;int ans = getCount(n);System.out.printf("共有%d种跳法", ans);}private static int getCount(int n) {return help(n);}private static int help(int n) {if(n == 1){return 1;}if(n == 2){return 2;}return help(n-1) + help(n-2);}
}

 

四、汉诺塔问题:

问题描述:

有三根柱子,编号为A、B、C,开始时在柱子A上有一些个圆盘,它们按照从下到上的顺序递增(最下面的最大,最上面的最小)。现在要将这些圆盘从柱子A移动到柱子C,中间可以借助柱子B,但有一些规则需要遵守:

  1. 每次只能移动一个圆盘。
  2. 移动过程中,大圆盘不能放在小圆盘上面。
public class Demo1 {static LinkedList<Integer> a = new LinkedList<>();static LinkedList<Integer> b = new LinkedList<>();static LinkedList<Integer> c = new LinkedList<>();public static void main(String[] args) {a.addLast(3);a.addLast(2);a.addLast(1);move(3, a, b, c);}private static void move(int n, LinkedList<Integer> a, LinkedList<Integer> b, LinkedList<Integer> c) {if(n == 0){return;}//转移n-1个到b - 要借助cmove(n-1, a, c, b);//将最大的移到Cc.add(a.removeLast());myPrint();//将n-1个到c - 要借助amove(n-1, b, a, c);}private static void myPrint() {System.out.println(a);System.out.println(b);System.out.println(c);System.out.println("===============");}
}

 

五:杨辉三角问题:

问题描述:有个三角形,每一行的该数等于上一行同列数+上一行前一列的数

①无记忆递归:
public class Demo2 {public static void main(String[] args) {int n = 6;print(n);}private static void printSpace(int n){for (int i = 0; i < n; i++) {System.out.print(" ");}}private static void print(int n) {for (int i = 0; i < n; i++) {printSpace((n-i-1)*2);for (int j = 0; j <= i; j++) {System.out.printf("%-4d", getElement(i, j));}System.out.println();}}private static int getElement(int row, int col){if(col == 0 || col == row){return 1;}return getElement(row-1, col-1) + getElement(row-1, col);}
}
②⭐记忆递归:
public class Demo1 {public static void main(String[] args) {int n = 6;print(n);}private static void printSpace(int n){for (int i = 0; i < n; i++) {System.out.print(" ");}}private static void print(int n) {int[][] cache = new int[n][];for (int i = 0; i < n; i++) {printSpace((n-i-1)*2);cache[i] = new int[i+1];for (int j = 0; j <= i; j++) {System.out.printf("%-4d", getElement(cache, i, j));}System.out.println();}}private static int getElement(int[][] cache, int row, int col){if(cache[row][col] > 0){return cache[row][col];}if(col == 0 || col == row){cache[row][col] = 1;return 1;}cache[row][col] = getElement(cache, row-1, col-1) + getElement(cache, row-1, col);return cache[row][col];}
}

 

六、猴子吃桃问题:

问题描述:

有一只猴子摘了一堆桃子,第一天它吃了其中的一半,并再多吃了一个;第二天它又吃了剩下的桃子的一半,并再多吃了一个;以后每天都吃了前一天剩下的一半并再多吃了一个。到第n天想再吃时,发现只剩下一个桃子。问这堆桃子原来有多少个?

public class MonkeyEatPeach {public static void main(String[] args) {int days = 9; // 假设猴子在第9天时发现只剩下一个桃子// 调用计算桃子数量的方法int result = calculatePeaches(days);// 输出结果System.out.println("猴子摘的桃子总数为:" + result);}// 计算桃子数量的方法public static int calculatePeaches(int days) {if(days == 1){return 1;}return (calculatePeaches(days - 1) + 1) * 2;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/197430.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【飞控调试】DJIF450机架+Pixhawk6c mini+v1.13.3固件+好盈Platinium 40A电调无人机调试

1 背景 由于使用了一种新的航电设备组合&#xff0c;在调试无人机起飞的时候遇到了之前没有遇到的问题。之前用的飞控&#xff08;Pixhawk 6c&#xff09;和电调&#xff08;Hobbywing X-Rotor 40A&#xff09;&#xff0c;在QGC里按默认参数配置来基本就能平稳飞行&#xff0…

【Linux】21、软中断、网络小包、SYN FLOOD 攻击、sar tcpdump

文章目录 一、通俗理解&#xff1a;从“取外卖”看中断二、软中断2.1 网卡收发数据包2.2 查看软中断和内核线程2.3 案例2.3.1 案例&#xff1a;动态库 sleep 导致软中断2.3.2 Nginx 进程的不可中断状态是系统的一种保护机制&#xff0c;可以保证硬件的交互过程不被意外打断。所…

SpringBoot使用DevTools实现后端热部署

&#x1f4d1;前言 本文主要SpringBoot通过DevTools实现热部署的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是青衿&#x1f947; ☁️博客首页&#xff1a;CSDN主页放风讲故事 &#x1f304;每日一句&…

docker 安装mongodb 实现 数据,日志,配置文件外挂

docker 安装mongodb 实现数据&#xff0c;日志&#xff0c;配置文件外挂 1 背景 最近开发了一个评论系统之前用mysql来存储数据&#xff0c;但是考虑到后期业务增大访问量也会增大&#xff0c;为了兼容这种高并发的场景&#xff0c;因此经过多方面的考虑&#xff0c;我们最终…

理论与实践相结合之Cisco Packet Tracer网络模拟器安装教程

简介 Packet Tracer是由思科设计的跨平台可视化仿真工具&#xff0c;它允许用户创建网络拓扑以模仿计算机网络和使用命令行界面来模拟配置思科路由器和交换机。Packet Tracer的用户界面为拖放式&#xff0c;允许用户根据自己的需要添加和删除模拟的网络设备。 Packet Tracer很…

RVC从入门到......

RVC变声器官方教程&#xff1a;10分钟克隆你的声音&#xff01;一键训练&#xff0c;低配显卡用户福音&#xff01;_哔哩哔哩_bilibili配音&#xff1a;AI逍遥散人&#xff08;已授权&#xff09;关注UP主并私信"RVC"&#xff08;三个字母&#xff09;自动获取一键训…

MySQL 的执行原理(一)

5.1 单表访问之索引合并 我们前边说过 MySQL 在一般情况下执行一个查询时最多只会用到单个二级 索引&#xff0c;但存在有特殊情况&#xff0c;在这些特殊情况下也可能在一个查询中使用到多个二 级索引&#xff0c;MySQL 中这种使用到多个索引来完成一次查询的执行方法称之为&…

IntelliJ IDEA 2023 v2023.2.5

IntelliJ IDEA 2023是一款功能强大的集成开发环境&#xff08;IDE&#xff09;&#xff0c;为开发人员提供了许多特色功能&#xff0c;以下是其特色介绍&#xff1a; 新增语言支持&#xff1a;IntelliJ IDEA 2023新增对多种编程语言的支持&#xff0c;包括Kotlin、TypeScript、…

局部指令和全局指令的注册和使用

全局指令 先写一个js文件 import store from /store const directivePlugin {install(Vue) {Vue.directive(checkBtn, {inserted(el, binding) {// el: 指令绑定的那个元素对象 dom// binding.value: 指令等于号后面绑定的表达式的值 v-if"xxx"// 拿到el 拿到v…

【机器学习12】集成学习

1 集成学习分类 1.1 Boosting 训练基分类器时采用串行的方式&#xff0c; 各个基分类器之间有依赖。每一层在训练的时候&#xff0c; 对前一层基分类器分错的样本&#xff0c; 给予更高的权重。 测试时&#xff0c; 根据各层分类器的结果的加权得到最终结果。 1.2 Bagging …

远程炼丹教程

【精选】深度学习远程炼丹&#xff1a;一文离线完成ubuntudockerpycharm环境配置_不能联网的电脑如何用docker配置深度学习环境_Yunlord的博客-CSDN博客文章浏览阅读2.6k次&#xff0c;点赞8次&#xff0c;收藏10次。本文详细讲解如何在离线服务器中安装dockerpycharm的远程深度…

java 实现串口通讯

1、引入依赖 <dependency><groupId>org.scream3r</groupId><artifactId>jssc</artifactId><version>2.8.0</version> </dependency>2、配置启动串口 Component public class ContextHolder implements ApplicationContextAw…

Windows网络「SSL错误问题」及解决方案

文章目录 问题方案 问题 当我们使用了神秘力量加持网络后&#xff0c;可能会和国内的镜像源网站的之间发生冲突&#xff0c;典型的有 Python 从网络中安装包&#xff0c;如执行 pip install pingouin 时&#xff0c;受网络影响导致无法完成安装的情况&#xff1a; pip config…

量化交易:建立趋势跟踪策略的五个指标

什么是趋势跟踪策略&#xff1f; 趋势跟踪策略是只需需顺势而为的策略&#xff0c;即在价格上涨时买入&#xff0c;在价格开始下跌时卖出。在趋势跟踪策略中&#xff0c;人们的目标不是预测或预测&#xff0c;而只是关注市场上的任何新兴趋势。 趋势是如何出现的&#xff1f;…

SQL INSERT INTO 语句详解:插入新记录、多行插入和自增字段

SQL INSERT INTO 语句用于在表中插入新记录。 INSERT INTO 语法 可以以两种方式编写INSERT INTO语句&#xff1a; 指定要插入的列名和值&#xff1a; INSERT INTO 表名 (列1, 列2, 列3, ...) VALUES (值1, 值2, 值3, ...);如果要为表的所有列添加值&#xff0c;则无需在SQL…

系列六、JVM的内存结构【栈】

一、产生背景 由于跨平台性的设计&#xff0c;Java的指令都是根据栈来设计的&#xff0c;不同平台的CPU架构不同&#xff0c;所以不能设计为基于寄存器的。 二、概述 栈也叫栈内存&#xff0c;主管Java程序的运行&#xff0c;是在线程创建时创建&#xff0c;线程销毁时销毁&…

LabVIEW编程开发NI-USRP

LabVIEW编程开发NI-USRP 可编程性是SDR的关键特性&#xff0c;它使人们能够将无线电外围设备转换为先进的无线系统。USRP是市场上最开放、最通用的SDR&#xff0c;可帮助工程师在主机和FPGA上使用各种软件开发工具构建系统。 有多种选项可用于对基于SDR的系统的主机进行编程。…

Pytorch D2L Subplots方法对画图、图片处理

问题代码 def show_images(imgs, num_rows, num_cols, titlesNone, scale1.5): #save """绘制图像列表""" figsize (num_cols * scale, num_rows * scale) _, axes d2l.plt.subplots(num_rows, num_cols, figsizefigsize) axes axes.flatten…

springMVC学习笔记-请求映射,参数绑定,响应,restful,响应状态码,springMVC拦截器

目录 概述 springMVC做了什么 springMVC与struts2区别 springMVC整个流程是一个单向闭环 springMVC具体的处理流程 springMVC的组成部分 请求映射 RequestMapping 用法 属性 1.value 2.method GET方式和POST方式 概述 HTTP给GET和POST做了哪些规定 GET方式&…

HTML5学习系列之实用性标记

HTML5学习系列之实用性标记 前言实用性标记高亮显示进度刻度时间联系信息显示方向换行断点标注 总结 前言 学习记录 实用性标记 高亮显示 mark元素可以进行高亮显示。 <p><mark>我感冒了</mark></p>进度 progress指示某项任务的完成进度。 <p…