算法 数据结构 斐波那契数列 递归实现斐波那契数列 斐波那契递归的优化 斐波那契数列递归求解 多路递归实现 斐波那契算法系列 数据结构(十一)
1. 什么是斐波那契数列:
-
之前的例子是每个递归函数只包含一个自身的调用,这称之为 single recursion
-
如果每个递归函数例包含多个自身调用,称之为 multi recursion
递推关系
下面的表格列出了数列的前几项
| F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | F10 | F11 | F12 | F13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 |
多路递归斐波那契代码实现1:
package com.nami.algorithm.study.day07;/*** beyond u self and trust u self.** @Author: lbc* @Date: 2023-09-06 9:29* @email: 594599620@qq.com* @Description: keep coding*/
public class Fibonacci {/*** 出现问题的,计算 n= 88 根本算不出来。多路递归一直在循环里面了。出不来 --!* @param n* @return*/public static int calculate(int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}int f1 = calculate(n - 1);int f2 = calculate(n - 2);return f1 + f2;}public static void main(String[] args) {// 时间复杂度: 2*f(n+1) -1// E(1.618N次方)System.out.println(calculate(88));}}
非递归实现2 --- LeetCode 70. 爬楼梯 计算爬楼梯共计多少种方法可达_不努力就种地~的博客-CSDN博客
之前写的爬楼梯解决方案:
public static int climbStairs(int n) {int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
这种方法直接用数组去存储前面计算的值,不用重复计算。没有出现上面n=88出现的计算缓慢问题
递归优化方案:
使用数组,存储之前计算的数据,减少计算次数。妙哉
package com.nami.algorithm.study.day07;import java.util.Arrays;/*** beyond u self and trust u self.** @Author: lbc* @Date: 2023-09-06 9:29* @email: 594599620@qq.com* @Description: keep coding*/
public class FastFibonacci {/*** 出现问题的,计算 n= 100000* 出现异常 StackOverflowError* 方法层级太深,会导致栈溢出** @param n* @return*/public static int calculate(int n) {// 初始化缓存// ==>记忆法// 空间换时间int[] cache = new int[n + 1];// 填充-1 标识未该值为计算Arrays.fill(cache, -1);cache[0] = 0;cache[1] = 1;return fibonacci(n, cache);}/*** 时间复杂度: O(n)* 增加额外空间成本** @param n* @param cache* @return*/private static int fibonacci(int n, int[] cache) {if (cache[n] != -1) {return cache[n];}int f1 = fibonacci(n - 1, cache);int f2 = fibonacci(n - 2, cache);cache[n] = f1 + f2;return cache[n];}public static void main(String[] args) {// n=88也有问题,出现-值// -2092787285System.out.println(calculate(88));}}
使用数组进行优化,也有一个问题,数组只有n-1, n-2两个值有用。对于计算之后,存储前面n-3的值没有了意义;
优化2 ==>尾递归:
尾递归(防止栈溢出) + 只取n-1, n-2的值流转
package com.nami.algorithm.study.day07;/*** 尾递归 斐波那契数列* beyond u self and trust u self.** @Author: lbc* @Date: 2023-09-06 9:29* @email: 594599620@qq.com* @Description: keep coding*/
public class TailRecFibonacci {/*** @param n* @return*/public static int calculate(int n) {return fibonacci(n, 0, 1);}private static int fibonacci(int n, int first, int second) {if (n == 0) {return first;}if (n == 1) {return second;}return fibonacci(n - 1, second, first + second);}public static void main(String[] args) {// n=47,出现-值// -1323752223// 18 3631 1903 + 11 3490 3170// n= 46 + n=45// int 最大值 21 4748 3647System.out.println(calculate(46));}}
为什么斐波那契数列会出现负值?
当n=88时,结果等于负数。排查发现:当n=46是正常的,n=47时,前面两个值的相加已经超过了int最大值int.max_value= 21 4748 3647 所以出现负数
如何根本上解决爆栈问题:
递归转for or while循环解决问题。
相关文章:
算法 数据结构 斐波那契数列 递归实现斐波那契数列 斐波那契递归的优化 斐波那契数列递归求解 多路递归实现 斐波那契算法系列 数据结构(十一)
1. 什么是斐波那契数列: 之前的例子是每个递归函数只包含一个自身的调用,这称之为 single recursion 如果每个递归函数例包含多个自身调用,称之为 multi recursion 递推关系 下面的表格列出了数列的前几项 F0F1F2F3F4F5F6F7F8F9F10F11F12…...
【面试经典150 | 双指针】两数之和
文章目录 写在前面Tag题目来源题目解读解题思路方法一:暴力枚举方法二:哈希表方法三:二分法方法四:双指针 知识回顾写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢…...
桥接模式简介
概念: 桥接模式是一种结构型设计模式,它将抽象和实现分离,使它们可以独立地变化。通过使用桥接模式,可以将一个类的抽象部分与其具体实现部分解耦,并且可以在运行时动态地选择不同的实现。 特点: 将抽象…...
零钱兑换00
题目链接 零钱兑换 题目描述 注意点 如果没有任何一种硬币组合能组成总金额,返回 -1可以认为每种硬币的数量是无限的 解答思路 动态规划从总金额1开始推出目标金额所需的最少硬币个数,任意某个金额所需的最少硬币个数可以由当前金额减去每种面额的硬…...
JavaScipt中如何实现函数缓存?函数缓存有哪些场景?
1、函数缓存是什么? 函数缓存就是将函数运行的结果进行缓存。本质上就是用空间(缓存存储)换时间(计算过程) 常用于缓存数据计算结果和缓存对象。 缓存只是一个临时的数据存储,它保存数据,以便将…...
android studio的Android Drawable Preview
Android Drawable Preview 应用后,如下图: 再也不用一个一个点开去看了 其他学习资料: 1、付费专栏《Android kotlin入门到进阶系列讲解》:https://blog.csdn.net/qq_35091074/category_11036895.html 2、免费专栏《Android kot…...
基于云计算的区域LIS系统系统源码
在医疗机构内部,院内实验室主要负责本院临床科室的检验,院内LIS系统必须满足实验室日常的标本处理入库、仪器联机、检验结果处理、报告打印、报告发布、检验信息统计、检验信息报告发布、标本流程、外部医疗机构检验报告调阅等工作。 在医疗机构间&#…...
VR农学虚拟仿真情景实训教学演示
首先,VR农学虚拟仿真情景实训教学提供了更为真实的实践环境。传统的农学实训往往受制于时间、空间和资源的限制,学生只能通过观察或简单的模拟来学习农业知识和技能。而借助虚拟现实技术,学生可以进入虚拟农场,与各种农作物、工具…...
sklearn中make_blobs方法:聚类数据生成器
sklearn中make_blobs()方法参数: n_samples:表示数据样本点个数,默认值100 n_features:是每个样本的特征(或属性)数,也表示数据的维度,默认值是2。默认为 2 维数据,测试选取 2 维数据也方便进行可视化展示…...
Win11自带微软输入法怎么输入π及其他希腊字母
如果用搜狗等第三方输入法的话就没有这些问题了,各种符号很方便。 自带的输入法输入 pi 和 pai 都不能正常输入 π \pi π 参考文章 https://www.cnblogs.com/qq-757617012/p/14078133.html 如果用自带的输入法可以采用以下方式 输入uuxl xl表示“希腊”&#x…...
关于MyBatisPlus框架下出现xml里面定义的方法无法被正确识别以及提示调用mysql存储过程时参数无效的问题
第一个问题:xml里面明明定义了方法A,但是通过IService接口调用A的时候,总提示无法将接口中定义的函数绑定到xml中的同名方法中(“Invalid bound statement (not found): com.aircas.sqlservice.mapper.SysTempIndexMapper.getRemo…...
vscode路径别名文件跳转解决办法
第一步:下载 1.在jsconfig.json中配置: {"compilerOptions": {"target": "es5","module": "esnext","baseUrl": "./","moduleResolution": "node","p…...
layui 富文本编辑器layedit 以及 图片转base64前端页面显示
js var index layui.layedit.build(noticeInformationContent, {area: [500px, 400px],uploadImage: {url: NI/uploadconimage //接口url, type: POST //默认post},hideTool: [image]});layui.form.verify({content: function (val) {layui.layedit.sync(index);var content …...
服务器给前端实时推送数据轻量化解决方案eventSource+Springboot
一、前端代码 body代码 <div id"result"></div>js代码 $(function(){if(typeof(EventSource) ! "undefined"){var source new EventSource("/demo/getTime");source.onmessage function(event) {console.log(event.data);$(&qu…...
数据结构与算法:数据结构基础
目录 数组 定义 形式 顺序存储 基本操作 读取元素 更新元素 插入元素 删除元素 扩容 初始化 时机 步骤 优劣势 链表 定义 单向链表 特点 双向链表 随机存储 基本操作 查找节点 更新节点 插入节点 删除元素 数组VS链表 栈与队列 栈 定义 基本操作…...
virtualbox虚拟机中安装FreeDOS系统和DJGPP编译环境
一、安装FreeDOS系统 1、从官网下载FreeDOS系统镜像,下载的压缩包中包含两个文件:后缀为.iso和.img的镜像 下载页面 http://www.freedos.org/download/ 直接下载链接 https://www.ibiblio.org/pub/micro/pc-stuff/freedos/files/distributions/1.…...
JAVASE事件监听
代码: import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Scanner;import javax.swing.JButton; import javax.…...
ubuntu14.04改静态ip
现在可能已经用ubuntu14.04的人已经不多了,这里讲一下Ubuntu14.04怎么改静态ip 第一步:输入ifconfig查看ip和子网掩码 第二步:输入route -n查看网关 上面ip是192.168.88.136,子网掩码是255.255.255.0,网关是192.168.…...
“文件的上传与下载:实现与优化“
目录 引言1.文件的上传2.文件的下载3. JRebel安装使用4. 文件批量上传总结 引言 在开发过程中,文件的上传与下载是常见的需求。本篇博客将以CSND为例,介绍文件上传与下载的常见方式,以及如何通过优化提升性能和用户体验。 1.文件的上传 使…...
uboot顶层Makefile前期所做工作说明三
一. uboot顶层 Makefile文件 uboot顶层 Makefile,就是 uboot源码工程的根目录下的 Makefile文件。 本文继续对 uboot顶层 Makefile的前期准备工作进行介绍。续上一篇文章内容的学习,如下: uboot顶层Makefile前期所做工作说明二_凌肖战的博…...
nli-distilroberta-base实际项目:高校招生简章关键条款与考生疑问逻辑关系库构建
nli-distilroberta-base实际项目:高校招生简章关键条款与考生疑问逻辑关系库构建 1. 项目背景与需求 高校招生简章通常包含大量专业条款和政策说明,每年都会收到大量考生关于条款理解的咨询。传统的人工解答方式存在几个痛点: 效率低下&am…...
从VGG到ResNet:为什么说‘残差块’是深度学习模型‘卷’层数的救命稻草?
从VGG到ResNet:残差连接如何重塑深度神经网络的设计哲学 2014年ImageNet竞赛上,VGGNet凭借其规整的3x3卷积堆叠结构一举夺魁,将图像识别准确率提升到新高度。正当整个计算机视觉领域沉浸在"更深就一定更好"的乐观情绪中时ÿ…...
【电赛实战利器】基于STM32F4与协方差修正的全数字锁相放大器设计与实测
1. 为什么你需要一个全数字锁相放大器? 在电子设计竞赛或者精密测量项目中,微弱信号检测总是让人头疼。想象一下,你要从一堆嘈杂的噪音中找出一个微弱的正弦波信号,就像在喧闹的菜市场里听清远处朋友的耳语。传统模拟锁相放大器需…...
告别网络依赖:用这个开源工具+高德离线包,5步搞定前端地图离线展示
前端开发者的离线地图解决方案:5步实现高德地图本地化部署 在紧急演示、内网开发或网络不稳定的环境中,依赖在线地图服务往往成为前端开发的痛点。我曾参与过一个政府内网项目,现场演示时因网络权限问题导致地图无法加载,最后不得…...
RWKV7-1.5B-g1a开源大模型落地:无需高端A100,RTX4090即可跑满多语言生成能力
RWKV7-1.5B-g1a开源大模型落地:无需高端A100,RTX4090即可跑满多语言生成能力 1. 模型简介 rwkv7-1.5B-g1a 是基于新一代 RWKV-7 架构的开源多语言文本生成模型,专为实际应用场景优化。这个1.5B参数的模型在保持出色生成能力的同时࿰…...
本地Cookie导出终极指南:Get cookies.txt LOCALLY 安全使用教程
本地Cookie导出终极指南:Get cookies.txt LOCALLY 安全使用教程 【免费下载链接】Get-cookies.txt-LOCALLY Get cookies.txt, NEVER send information outside. 项目地址: https://gitcode.com/gh_mirrors/ge/Get-cookies.txt-LOCALLY 你是否曾担心浏览器Coo…...
OpenClaw对接GLM-4.7-Flash:模型版本管理指南
OpenClaw对接GLM-4.7-Flash:模型版本管理指南 1. 为什么需要关注模型版本管理 上周我在调试一个自动化文档处理流程时,遇到了一个奇怪的现象:同样的OpenClaw脚本,前一天还能完美运行的文档摘要功能,第二天突然开始输…...
Systemd配置文件修改后不生效?试试这个命令比重启更高效
Systemd配置热更新实战:如何用daemon-reexec替代服务重启 在Linux系统管理中,systemd作为现代init系统的代表,其配置调整是管理员日常工作的核心部分。但许多工程师在修改/etc/systemd/system.conf这类全局配置后,往往陷入两难&am…...
OpenPPL之二,优化器里面的算子融合
算子融合的执行时机 完整的时间线 模型加载阶段(一次) 运行时阶段(多次推理)↓ ↓ ┌─────────────────────┐ ┌─────────────┐ │ 1. 解析ON…...
OpenClaw任务监控:GLM-4.7-Flash执行状态可视化方案
OpenClaw任务监控:GLM-4.7-Flash执行状态可视化方案 1. 为什么需要任务监控? 去年冬天的一个深夜,我被手机警报惊醒——OpenClaw正在执行的周报生成任务已经连续失败了三次。打开电脑检查日志时才发现,原来是本地部署的GLM-4.7-…...
