当前位置: 首页 > news >正文

一分钟学算法-递归-斐波那契数列递归解法及优化

请添加图片描述

一分钟学一个算法题目。

今天我们要学习的是用递归算法求解斐波那契数列。

首先我们要知道什么是斐波那契数列。

斐波那契数列,又称黄金分割数列,是一个经典的数学数列,其特点是第一项,第二项为1,后面每个数字都是前两个数字之和。推导过程如视频所示,非常非常简单。

知道了斐波那契数列的定义后,我们将其代入到递归问题的分析当中。

首先确定边界条件,就是第一项和第二项为1,接着确定递归关系,后一项等于前两项的和。确定了上面这些关系,我们就可以写出下面的代码了。

def fib(x):# 边界条件if x==1 or x==2: return 1# 递归关系return fib(x-2)+fib(x-1)print(fib(1))
print(fib(2))
print(fib(3))
print(fib(4))
print(fib(5))
print(fib(6))

没错,去掉注释和空行后只有三行代码,简洁精炼是递归问题的共性,你学习过肯定深有体会。下面我们稍微解读下代码,这是一个求解斐波那契数列第n项数字的函数,函数名为fib,接受一个参数n。
如果n等于1或者2,那么就返回1,否则就返回fib(n-2)与fib(n-1)的和,怎么样,脑子转过来弯了吗?没错,就是这么简单。我们来尝试运行使用函数检验一下正确性,发现都输出了正确结果。

但是这个函数还有很大的优化空间,在哪里呢?没错,递归算法让我们使用简洁的代码解决复杂的问题。但他的时间复杂度很高,一不小心没做好边界与转换关系判断就会导致无限循环或者栈溢出。

我们以此题为例,假如我们要求解斐波那契数列的第一百项数字,那麽我们会得到这张调用关系图,同一项会被重复计算非常非常多次。所以你运行此函数可能会导致很长时间都计算不出结果。

那么,我们该如何优化呢?
我们该如何避免重复计算某一项的值呢?

我们可以在计算出每一项的时候,把计算结果存到一个字典里。这样我们在每次计算前先去字典中寻找这一项,如果有值,那么直接拿出来使用,如果没有,再计算它。

这样的话我们就可以保证每一项仅被计算一次。运行时间也将会大大缩短。按照以上思路我们对代码进行如下变化。

def fib(n):# 边界条件if n==1 or n==2: return 1if hash.get(n,0):return hash.get(n)# 递归关系ans=fib(n-2)+fib(n-1)hash[ans]=ansreturn anshash={}

在代码中我们增加了以下变化:
每次计算某一项时先去集合中查询,如果已经计算过,那么直接返回值,如果没有,则计算,并且在返回值之前先在集合中记录一下。

这样代码的算法复杂度已经优化了很多了,没有优化版本求解第70项都非常费力,现在优化后已经可以轻松算出第100项了。但要想算出第一百项还是需要很久时间。

因为其中还存在大量的分支判断。

而且此解法还远远不是最优解法,关注up主,我们下集就来讲讲更快的方法。

相关文章:

一分钟学算法-递归-斐波那契数列递归解法及优化

一分钟学一个算法题目。 今天我们要学习的是用递归算法求解斐波那契数列。 首先我们要知道什么是斐波那契数列。 斐波那契数列,又称黄金分割数列,是一个经典的数学数列,其特点是第一项,第二项为1,后面每个数字都是前…...

选择Rust,并在Ubuntu上使用Rust

在过去的 8 年里,Rust 一直是开发人员最喜欢的语言,并且越来越被各种规模的软件公司采用。然而,它的许多高级规则和抽象创造了一个陡峭的初始学习曲线,这可能会给人留下 Rust 是少数人的保留的印象,但这与事实相去甚远…...

SVM详解

公式太多了,就用图片用笔记呈现,SVM虽然算法本质一目了然,但其中用到的数学推导还是挺多的,其中拉格朗日约束关于α>0这块证明我看了很长时间,到底是因为悟性不够。对偶问题也是,用了一个简单的例子才明…...

mysql全文检索使用

数据库数据量10万左右,使用like %test%要耗费30秒左右,放弃该办法 使用mysql的全文检索 第一步:建立索引 首先修改一下设置: my.ini中ngram_token_size 1 可以通过 show variables like %token%;来查看 接下来建立索引:alter table 表名 add f…...

opencv 进阶17-使用K最近邻和比率检验过滤匹配(图像匹配)

K最近邻(K-Nearest Neighbors,简称KNN)和比率检验(Ratio Test)是在计算机视觉中用于特征匹配的常见技术。它们通常与特征描述子(例如SIFT、SURF、ORB等)一起使用,以在图像中找到相似…...

Mac Flutter web环境搭建

获取 Flutter SDK 下载以下安装包来获取最新的 stable Flutter SDK将文件解压到目标路径, 比如: cd ~/development $ unzip ~/Downloads/flutter_macos_3.13.0-stable.zip 配置 flutter 的 PATH 环境变量: export PATH"$PATH:pwd/flutter/bin" // 这个命…...

在外SSH远程连接macOS服务器

文章目录 前言1. macOS打开远程登录2. 局域网内测试ssh远程3. 公网ssh远程连接macOS3.1 macOS安装配置cpolar3.2 获取ssh隧道公网地址3.3 测试公网ssh远程连接macOS 4. 配置公网固定TCP地址4.1 保留一个固定TCP端口地址4.2 配置固定TCP端口地址 5. 使用固定TCP端口地址ssh远程 …...

Dockerfile文件详细

Dockerfile 是一个文本文件,里面包含组装新镜像时用到的基础镜像和各种指令,使用dockerfile 文件来定义镜像,然后运行镜像,启动容器。 dockerfile文件的组成部分 一个dockerfile文件包含以下部分: 基础镜像信息&…...

C语言学习系列-->看淡指针(3)

文章目录 一、字符指针变量二、数组指针变量2.1 概述2.2 数组指针初始化 三、二维数组传参本质四、函数指针五、typedef关键字六、函数指针数组 一、字符指针变量 在指针的类型中我们知道有⼀种指针类型为字符指针 char* 一般使用&#xff1a; #include<stdio.h>int main…...

Java抽象类详解

抽象类 抽象类的概念 在面向对象的概念中&#xff0c;所有的对象都是通过类来描绘的&#xff0c;但是反过来&#xff0c;并不是所有的类都是来描绘对象的&#xff0c;如果一个类中没有包含足够的信息来描绘一个具体的对象&#xff0c;这样的类就是抽象类。比如&#xff1a; 说…...

06-微信小程序-注册程序-场景值

06-微信小程序-注册程序 文章目录 注册小程序参数 Object object案例代码 场景值场景值作用场景值列表案例代码 注册小程序 每个小程序都需要在 app.js 中调用 App 方法注册小程序实例&#xff0c;绑定生命周期回调函数、错误监听和页面不存在监听函数等。 详细的参数含义和使…...

多种方法实现 Nginx 隐藏式跳转(隐式URL,即浏览器 URL 跳转后保持不变)

多种方法实现 Nginx 隐藏式跳转(隐式URL,即浏览器 URL 跳转后保持不变)。 一个新项目,后端使用 PHP 实现,前端不做路由,提供一个模板,由后端路由控制。 Route::get(pages/{name}, [\App\Http\Controllers\ResourceController::class, getResourceVersion])...

视频汇聚云平台EasyCVR视频监控管理平台进行SDN转推的操作步骤

视频汇聚/视频云存储/集中存储/视频监控管理平台EasyCVR能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;实现视频资源的鉴权管理、按需调阅、全网分发、云存储、智能分析等&#xff0c;视频智能分析平台EasyCVR融合性强、开放度…...

SQL 语句继续学习之记录二

三&#xff0c; 聚合与排序 对表进行聚合查询&#xff0c;即使用聚合函数对表中的列进行合计值或者平均值等合计操作。 通常&#xff0c;聚合函数会对null以外的对象进行合计。但是只有count 函数例外&#xff0c;使用count(*) 可以查出包含null在内的全部数据行数。 使用dis…...

【Python原创设计】基于Python Flask 机器学习的全国+上海气象数据采集预测可视化系统-附下载链接以及详细论文报告,原创项目其他均为抄袭

基于Python Flask 机器学习的全国上海气象数据采集预测可视化系统 一、项目简介二、开发环境三、项目技术四、功能结构五、运行截图六、功能实现七、数据库设计八、源码获取 一、项目简介 在信息科技蓬勃发展的当代&#xff0c;我们推出了一款基于Python Flask的全国上海气象数…...

Unity进阶–通过PhotonServer实现人物选择和多人同步–PhotonServer(四)

文章目录 Unity进阶–通过PhotonServer实现人物选择和多人同步–PhotonServer(四)服务端客户端 Unity进阶–通过PhotonServer实现人物选择和多人同步–PhotonServer(四) 服务端 服务端结构如下&#xff1a; UserModel using System; using System.Collections.Generic; usin…...

【Go 基础篇】Go语言获取用户终端输入:实现交互式程序的关键一步

介绍 在许多编程场景中&#xff0c;我们需要编写交互式程序&#xff0c;以便用户可以在终端中输入数据并与程序进行交互。Go语言提供了丰富的方式来获取用户终端输入&#xff0c;使得编写交互式程序变得简单而有趣。本篇博客将深入探讨Go语言中获取用户终端输入的各种方法&…...

学习笔记:Opencv实现拉普拉斯图像锐化算法

2023.8.19 为了在暑假内实现深度学习的进阶学习&#xff0c;Copy大神的代码&#xff0c;记录学习日常 图像锐化的百科&#xff1a; 图像锐化算法-sharpen_lemonHe_的博客-CSDN博客 在环境配置中要配置opencv&#xff1a; pip install opencv-contrib-python Code and lena.png…...

如何在前端实现WebSocket发送和接收UDP消息(多线程模式)

目录 简介&#xff1a;步骤1&#xff1a;创建WebSocket连接步骤2&#xff1a;创建Web Workers步骤3&#xff1a;发送和接收UDP消息&#xff08;多线程模式&#xff09;结束语&#xff1a; 简介&#xff1a; 本文将继续介绍如何在前端应用中利用WebSocket技术发送和接收UDP消息…...

【微服务】一文了解 Nacos

一文了解 Nacos Nacos 在阿里巴巴起源于 2008 2008 2008 年五彩石项目&#xff08;完成微服务拆分和业务中台建设&#xff09;&#xff0c;成长于十年双十一的洪峰考验&#xff0c;沉淀了简单易用、稳定可靠、性能卓越的核心竞争力。 随着云计算兴起&#xff0c; 2018 2018 20…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

flow_controllers

关键点&#xff1a; 流控制器类型&#xff1a; 同步&#xff08;Sync&#xff09;&#xff1a;发布操作会阻塞&#xff0c;直到数据被确认发送。异步&#xff08;Async&#xff09;&#xff1a;发布操作非阻塞&#xff0c;数据发送由后台线程处理。纯同步&#xff08;PureSync…...