由斐波那契数列探究递推与递归
斐波那契数列定义:
斐波那契数列大家都非常熟悉。它的定义是:

对于给定的整数 x ,我们希望求出: f ( 1 ) + f ( 2 ) + … + f ( x ) f(1)+f(2)+…+f(x) f(1)+f(2)+…+f(x) 的值。
有两种方法,分别是递推(迭代)与递归
具体解释如下图

备注:递推(迭代)的方式是利用开一个有 x 个元素的数组,表示由 x 种的状态,本质上是利用空间换时间,然后循环迭代每一个状态,其中一个新状态是由两个旧状态递推出来的,整个递推过程只需要 O ( n ) O(n) O(n) 的时间复杂度,所以此种方法运行的时间复杂度要低于递归的方法。
递归的方法更像是一种暴搜(暴力搜索每一种状态),所有搜索到的状态构成一颗递归搜索树,搜索的次数就是所有树上的节点的个数,可以看到递归搜索树的节点树远大于循环迭代次数,其时间复杂度大约为 O ( 2 n − 2 ) O(2^{n - 2}) O(2n−2) 。
代码:
方法一:递推(迭代)
时间复杂度 O ( n ) O(n) O(n)
typedef long long ll;
const int N = 70;ll fib_dp(int x) //递推
{vector<ll> dp(N,0);dp[0] = 0,dp[1] = 1;for (int i = 2;i <= x;i ++ ) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[x];
}
方法二:递归
时间复杂度 O ( 2 n − 2 ) O(2^{n - 2}) O(2n−2)
typedef long long ll;
const int N = 70;ll fib_recursion(int x) //递归
{if (!x) return 0;else if (x == 1 || x == 2) return 1;else {return fib_recursion(x - 1) + fib_recursion(x - 2); //后序遍历的写法}
}
相关文章:
由斐波那契数列探究递推与递归
斐波那契数列定义: 斐波那契数列大家都非常熟悉。它的定义是: 对于给定的整数 x ,我们希望求出: f ( 1 ) f ( 2 ) … f ( x ) f(1)f(2)…f(x) f(1)f(2)…f(x) 的值。 有两种方法,分别是递推(迭代)与递归 具体解释如下图 备注…...
红队打靶练习:IMF: 1
目录 信息收集 1、arp 2、nmap 3、nikto 目录探测 gobuster dirsearch WEB 信息收集 get flag1 get flag2 get flag3 SQL注入 漏洞探测 脱库 get flag4 文件上传 反弹shell 提权 get flag5 get flag6 信息收集 1、arp ┌──(root㉿ru)-[~/kali] └─# a…...
密码管理局以及什么是密评?为什么要做密评(商用密码应用安全性评估)?
文章目录 密码管理局以及什么是密评?为什么要做密评?关于密码管理局国家密码管理局属于什么级别?什么是密评?密评发展史为什么要做密评?目前密码应用的几个问题密评对象不做“密评”或密评不合格有什么影响?如何才能顺利通过密评?密评的相关标准参考密码管理局以及什么是…...
六、Datax通过json字符串运行
Datax通过json字符串运行 一、场景二、代码实现 一、场景 制作一个web应用,在页面上配置一个json字符串,保存在数据库里面。在执行json的时候,动态在本地创建一个json文件后执行,并识别是否成功,将执行过程保存在数据…...
关于数据库
目录 一 什么是数据库(DB) 二 什么是数据库管理系统(DBMS) 三 数据库的作用/好处 一 什么是数据库(DB) 简单理解,数据库是存放数据的地方,就像冰箱是存放冷鲜食品的地方。 数据是数据存储的基本对象,而数据分为多…...
洛谷C++简单题小练习day14—闰年推算小程序
day14--闰年推算小程序--2.18 习题概述 题目描述 输入 x,y,输出 [x,y] 区间中闰年个数,并在下一行输出所有闰年年份数字,使用空格隔开。 输入格式 输入两个正整数 x,y,以空格隔开。 输出格式 第一行输出一个正整数…...
房企关注的典型数字化场景之一:数字营销
过去在增量时代下,房企的模式是“拿地-开发-卖房-拿地”,谁拿的地多、卖得快、利润高,谁“活得好”。而进入存量时代,加上政策调控影响,房企需要将核心竞争力转向精细化、多元化运营。 根据克而瑞数据统计,…...
BMS再进阶(新能源汽车电池管理系统)
引言 一文入门BMS(电池管理系统)_bms电池管理-CSDN博客 BMS进阶(Type-C、PD快充、充电IC、SOC算法、电池管理IC)_充电ic asi aso功能-CSDN博客 本文是上面两篇博客的续篇,之前都是讲解一些BMS基本原理,…...
K8s Deployment挂载ConfigMap权限设置
目录 样例 1. 样例 …… volumes: - configMap:defaultMode: 420name: ${Existed_configmap_name} …… 其中“defaultMode: 420”是设置权限的 2. 解析 在K8s(Kubernetes)中,defaultMode是用来设置Configmap挂载后的文件权限࿰…...
百度智能云分布式数据库 GaiaDB-X 与龙芯平台完成兼容认证
近日,百度智能云的分布式关系型数据库软件 V3.0 与龙芯中科技术股份有限公司的龙芯 3C5000L/3C5000 处理器平台完成兼容性测试,功能与稳定性良好,获得了龙架构兼容互认证证书。 龙芯系列处理器 通用 CPU 处理器是信息产业的基础部件…...
模拟电子技术——振荡器基本原理、RC桥式振荡器、矩形波发生电器
文章目录 前言一、振荡器什么是振荡器振荡器的基本电路结构振荡条件起振条件和稳幅原理 二、RC桥式振荡器什么是RC桥式振荡器RC串并联网络的选频特性振荡条件完整频率特性曲线举例 三、矩形波发生电器什么是矩形波发生电路稳态与暂态PWM脉宽调制矩形波发生电路基本组成 总结 前…...
Vue3+Vite+TS+Pinia+ElementPlus+Router+Axios创建项目
目录 初始项目组成1. 创建项目1.1 下载项目依赖1.2 项目自动启动1.3 src 别名设置vite.config.ts配置文件tsconfig.json配置若新创项目ts提示 1.4 运行测试 2. 清除默认样式2.1 样式清除代码下载2.2 src下创建公共样式文件夹style2.3 main.js中引入样式2.4 安装sass解析插件 2.…...
VMware虚拟机安装CentOS7
对于系统开发来说,开发者时常会需要涉及到不同的操作系统,比如Windows系统、Mac系统、Linux系统、Chrome OS系统、UNIX操作系统等。由于在同一台计算机上安装多个系统会占据我们大量的存储空间,所以虚拟机概念应运而生。本篇将介绍如何下载安…...
Avalonia学习(二十四)-系统界面
目前项目式练习,界面内容偏多,所以不给大家贴代码了,可以留言交流。此次为大家展示的是物联项目的例子,仅仅是学习,我把一些重点列举一下。 界面无边框 以前的样例主要是通过实现控件来完成的,前面已经有窗…...
深入解析鸿蒙系统的页面路由(Router)机制
鸿蒙系统以其独特的分布式架构和跨设备的统一体验而备受瞩目。在这个系统中,页面路由(Router)机制是连接应用各页面的关键组成部分。本文将深入探讨鸿蒙系统的页面路由,揭示其工作原理、特点以及在应用开发中的实际应用。 1. 实现…...
MCU中断响应流程及注意事项
本文介绍MCU中断响应流程及注意事项。 1.中断响应流程 中断响应的一般流程为: 1)断点保护 硬件操作,将PC,PSR等相关寄存器入栈保护 2)识别中断源 硬件操作,识别中断的来源,如果多个中断同时发生,高优…...
基于Java SSM框架实现网上报名系统项目【项目源码+论文说明】计算机毕业设计
基于java的SSM框架实现网上报名系统演示 摘要 随着互联网时代的到来,同时计算机网络技术高速发展,网络管理运用也变得越来越广泛。因此,建立一个B/S结构的网上报名系统,会使网上报名系统工作系统化、规范化,也会提高网…...
Eclipse - Formatter
Eclipse - Formatter References Window -> Preferences -> C/C -> Code Style -> Formatter BSD/Allman [built-in] or K& R [built-in] References [1] Yongqiang Cheng, https://yongqiang.blog.csdn.net/...
算法练习-01背包问题【含递推公式推导】(思路+流程图+代码)
难度参考 难度:困难 分类:动态规划 难度与分类由我所参与的培训课程提供,但需 要注意的是,难度与分类仅供参考。且所在课程未提供测试平台,故实现代码主要为自行测试的那种,以下内容均为个人笔记࿰…...
Eclipse - Format Comment
Eclipse - Format & Comment 1. Correct Indentation2. Format3. Toggle Comment4. Add Block Comment5. Remove Block CommentReferences 1. Correct Indentation Ctrl A: 选择全部代码 Ctrl I: 校正缩进 or right-click -> Source -> Correct Indentation 2. F…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
