Java 递归计算斐波那契数列指定位置上的数字
Java 递归计算斐波那契数列指定位置上的数字
- 一、原理
- 二、代码实现
- 三、运行结果
一、原理
斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称“兔子数列”,其数值为:1、1、2、3、5、8、13、21、34……
在数学上,这一数列以如下递推的方法定义:F(0)=1,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)。
二、代码实现
要计算第 n 个斐波那契数列的数字,我们可以使用以下递归函数:
public class MyClass {public static void main(String[] args){int n = 10;System.out.println("斐波那契数列第 " + n + " 个数为 " + Fibonacci(n));}//递归 n代表第几个数public static int Fibonacci(int n) {//前两个数为 1//第三个数及后面的数为前面两数之和//如果输入的 n 不合法将返回 -1if (n == 1 || n == 2) {return 1;} else if (n > 2) {return Fibonacci(n - 1) + Fibonacci(n - 2);} else {return -1;}}}
时间复杂度:
- 最好情况下,当
n等于1或2时,直接返回1,时间复杂度为O(1)。 - 最坏情况下,当
n大于2时,需要递归调用Fibonacci()函数计算前两个数的和,时间复杂度为O(2^n)。因为每次递归调用会产生两个子问题,每个子问题又会产生两个更小的子问题,以此类推,直到递归到n等于1或2。 - 平均情况下,时间复杂度也是
O(2^n),因为每个数都需要通过递归调用计算得到。
空间复杂度:
- 由于递归调用会在堆栈中保存每次调用的局部变量和返回地址,所以空间复杂度取决于递归的深度。在最坏情况下,递归深度为
n,所以空间复杂度为O(n)。
综上所述,该递归实现的斐波那契数列函数的时间复杂度为指数级的 O(2^n),空间复杂度为线性的 O(n)。由于指数级的时间复杂度,在计算较大的斐波那契数时,递归实现会变得非常慢。
三、运行结果
斐波那契数列第 10 个数为 55
相关文章:
Java 递归计算斐波那契数列指定位置上的数字
Java 递归计算斐波那契数列指定位置上的数字 一、原理二、代码实现三、运行结果 一、原理 斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多斐波那契(Leonardo Fibonacci)以兔子繁殖为…...
ai数字人透明屏的应用场景有哪些?
AI数字人透明屏的应用场景: 银行、保险、售楼处等接待场景:AI数字人透明屏可以作为接待员,提供详细的信息和导航,提高客户体验和服务效率。 商业街、购物中心等场所:AI数字人透明屏可以作为导购员,提供商品…...
一、1、Hadoop的安装与环境配置
安装JDK: 首先检查Java是否已经安装: java -version 如果没有安装,点击链接https://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html 并选择相应系统以及位数下载(本文选择jdk-8u381-linux-x64…...
剑指YOLOv7改进最新MPDIoU损失函数(23年7月首发论文):论文实测YOLOv7模型涨点,超越现有多种G/D/C/EIoU,高效准确的边界框回归的损失
💡本篇内容:剑指YOLOv7改进最新MPDIoU损失函数(23年7月首发论文):论文实测YOLOv7模型涨点,超越现有多种G/D/C/EIoU,高效准确的边界框回归的损失 💡🚀🚀🚀本博客 改进源代码改进 适用于 YOLOv7 按步骤操作运行改进后的代码即可 💡:重点:该专栏《剑指YOLOv7原…...
前端JavaScript面试100问(上)
1、解释一下什么是闭包 ? 闭包:就是能够读取外层函数内部变量的函数。闭包需要满足三个条件: 访问所在作用域;函数嵌套;在所在作用域外被调用 。 优点: 可以重复使用变量,并且不会造成变量污染 。缺点&am…...
C语言第九课------------------数组----------------C中之将
作者前言 作者介绍: 作者id:老秦包你会, 简单介绍: 喜欢学习C语言和python等编程语言,是一位爱分享的博主,有兴趣的小可爱可以来互讨 个人主页::小小页面 gitee页面:秦大大 一个爱分享的小博主 欢迎小可爱…...
MySQL的安装
掌握在Windows系统中安装MySQL数据库 MySQL的介绍 MySQL数据库管理系统由瑞典的DataKonsultAB公司研发,该公司被Sun公司收购,现在Sun公司又被Oracle公司收购,因此MySQL目前属于 Oracle 旗下产品。MySQL 软件采用了双授权政策,分…...
在Chrome(谷歌浏览器)中安装Vue.js devtools开发者工具及解决Vue.js not detected报错
文章目录 一、Vue.js devtools开发者工具安装1.打开谷歌浏览器——点击扩展程序——选择管理扩展程序2.先下载添加一个谷歌助手到扩展程序中(根据提示进行永久激活)3.点击谷歌浏览器的应用商店4.输入Vue.js devtools——搜索——选择下载 二、解决Vue.js…...
用Python实现概率矩阵分解(PMF)算法在MovieLens ml-100k数据集上构建精确的推荐系统:深入理解GroupLens数据的操作
第一部分:推荐系统的重要性以及概率矩阵分解的介绍 在如今的数字化时代,推荐系统在我们的日常生活中起着重要的作用。无论我们在哪个电商网站上购物,哪个音乐平台听歌,或者在哪个电影网站看电影,都会看到推荐系统的身影。它们根据我们的喜好和行为,向我们推荐可能喜欢的…...
WPF icon的设置
想给控件设置个圆形图片,代码如下: <Setter Property"Icon"><Setter.Value><Image Source"/WpfApp1;component/Resource/1.ico" Width"16" Height"16"/></Setter.Value></Setter&…...
使用frp中的xtcp映射穿透指定服务实现不依赖公网ip网速的内网穿透p2p
使用frp中的xtcp映射穿透指定服务实现不依赖公网ip网速的内网穿透p2p 管理员Ubuntu配置公网服务端frps配置service自启(可选) 配置内网服务端frpc配置service自启(可选) 使用者配置service自启(可选) 效果 通过frp实现内网client访问另外一个内网服务器 管理员 1)…...
2023-07-28 LeetCode每日一题(并行课程 III)
2023-07-28每日一题 一、题目编号 2050. 并行课程 III二、题目链接 点击跳转到题目位置 三、题目描述 给你一个整数 n ,表示有 n 节课,课程编号从 1 到 n 。同时给你一个二维整数数组 relations ,其中 relations[j] [prevCoursej, next…...
8.11 PowerBI系列之DAX函数专题-TopN中实现N的动态
需求 实现 1 ranking by amount rankx(allselected(order_2[产品名称]),[total amount]) 2 rowshowing_boolean var v_ranking [ranking by amount] var v_topN-no [topN参数 值] var v_result int( v_ranking < v_topN_no) return v_result 3 将度量值2放入视觉对象筛…...
后端性能测试的类型
目录 性能测试的类型 负载测试(load testing) 压力测试(Stress Testing) 可扩展性测试( 尖峰测试(Spike Testing) 耐久性测试(Endurance Testing) 并发测试(Concurrency Testing) 容量测试(Capacity Testing) 资料获取方法 性能测试的类型 性能测试:确定软…...
关闭Tomcat的日志输出
要关闭Tomcat的日志输出,您可以在Tomcat的配置文件中进行相应的调整。具体地说,您可以通过修改logging.properties文件来关闭Tomcat的日志输出。这个文件通常位于Tomcat的conf目录下。请按照以下步骤进行: 打开Tomcat安装目录,找…...
express 路由匹配和数据获取
express配置路由只需要通过app.method(url,func)来配置,其中url配置和其中的参数获取方法不同 直接写全路径 路由中允许存在. get请求传入的参数 router.get("/home", (req, res) > {res.status(200).send(req.query); });通过/home?a1会收到对象…...
62 | Python 操作 PDF
文章目录 Python 操作 PDF 教程1. 安装 PyPDF22. 读取 PDF 文件3. 创建 PDF 文件4. 修改 PDF 文件练习题1. 创建一个新的 PDF 文件,其中包含两个页面。第一个页面包含一段文本和一张图片,第二个页面包含一个表格。2. 打开练习题中创建的 PDF 文件,并将第一个页面中的文本修改…...
[SQL挖掘机] - 左连接: left join
介绍: 左连接是一种多表连接方式,它以左侧的表为基础,并返回满足连接条件的匹配行以及左侧表中的所有行,即使右侧的表中没有匹配的行。左连接将左表的每一行与右表进行比较,并根据连接条件返回结果集。 左连接的工作原理如下&am…...
Android 之 使用 SoundPool 播放音效
本节引言: 第九章给大家带来的是Android中的多媒体开发,与其说是多媒体开发还不如是多媒体相关API的 的使用,说下实际开发中我们做了一些和多媒体搭边的东西:拍照,录音,播放音乐,播放视频... 嗯…...
防火墙的ALG、NAT、双机热备知识点详解
具体的NAT和双机热备实验请到:NAT与双机热备实验 目录 1、ALG 2、NAT ALG 3、NAT域间双向转换 4、NAT域内双向转换 5、双出口NAT 6、防火墙的双机热备 解决方案1:VGMP 6.1 双机热备份技术产生的背景: 6.2 VRRP在多区域防火墙组网中的…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
