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

数据结构----结构--线性结构--递归

数据结构----结构–线性结构–递归

1.递归的概念

递归:将一个问题拆解成解决方案完全相同的子问题,并且有一个明确的终点

看如下递归代码理解一下递归

void fun(int n){if(n==4){printf("%d",n);return;}fun(n+1);printf("%d",n);
}int main(){int a=1;fun(a);//输出的结果为 4 3 2 1
}

二.斐波那契数列

1.用递归实现斐波那契数列

int Fib(int n) {if(n==0) return;if (n==1||n==2) {return 1;}return Fib(n - 1)+ Fib(n - 2);}

优化

保存已经算过的递归结果

时间复杂度O(n)

空间复杂度O(递归的深度)

2.用循环实现斐波那契数列

int Fib(int n) {if (n == 0) return;if (n == 1 || n == 2) {return 1;}int a = 1;//n-2int b = 1;//n-1int c = 0;//nfor (int i = 3; i <= n; i++) {c = a + b;a = b;b = c;}return c;
}

时间复杂度O(n)

空间复杂度O(1)

3.青蛙跳台阶问题(网址https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/)

题目:

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

分析:

这道题就是斐波那契数列的变形

每一次都可以选择跳1级还是2级,

拿三阶台阶来说 它的总方法就是跳二阶台阶的方法加上跳一阶台阶方法 F(3)=F(2)+F(1)

拿四阶台阶来说 它的总方法就是跳三阶台阶的方法加上跳二阶台阶方法 F(4)=F(3)+F(2)

依次类推

F(n)=F(n-1)+F(n-2)

这里注意F(1)=1 ,F(2)=2

代码为

//这里的代码是c语言下的
int numWays(int n) {if (n == 1 || n == 0) {return 1 % (1000000007);}if (n == 2) {return 2 % (1000000007);}int a = 1;//n-2 台阶的方法int b = 2;//n-1 台阶的方法int c=0;//n 台阶的方法for (int i = 3; i <= n; i++) {c = (a + b)% 1000000007;a = b% 1000000007;b = c% 1000000007;}return c % 1000000007;
}

相关文章:

数据结构----结构--线性结构--递归

数据结构----结构–线性结构–递归 1.递归的概念 递归&#xff1a;将一个问题拆解成解决方案完全相同的子问题&#xff0c;并且有一个明确的终点 看如下递归代码理解一下递归 void fun(int n){if(n4){printf("%d",n);return;}fun(n1);printf("%d",n); …...

在Windows批处理程序中实现延时功能

方法1&#xff1a;使用PowerShell echo off:: 使用 PowerShell 的 Start-Sleep 命令来实现精确延时 powershell -command "Start-Sleep -Milliseconds 3000"echo Delay complete. 不过&#xff0c;通常Win7专业版和旗舰版中都会默认安装了PowerShell,但是标准版和家…...

Java基础入门篇——Java变量类型的转换和运算符(七)

目录 一、变量类型 1.1自动类型转换&#xff08;隐式转换&#xff09; 1.2 强制类型转换&#xff08;显式转换&#xff09; 1.3类型转换的其他情况 二、运算符 2.1算术运算符 2.2比较运算符 2.3逻辑运算符 2.4位运算符 三、总结 在Java中&#xff0c;变量类型的转换…...

20230807通过ffmpeg将DTS编码的AUDIO音频转换为AAC编码

20230807通过ffmpeg将DTS编码的AUDIO音频转换为AAC编码 2023/8/7 20:04 ffmpeg dts 转AAC 缘起&#xff1a;由于网上找的电影没有中文字幕&#xff0c;有内置的英文字幕&#xff0c;但是还是通过剪映/RP2023识别一份英文字幕备用&#xff01; I:\Downloads\2005[红眼航班]Red E…...

一生一芯1——windows与Ubuntu双系统安装

UltraISO下载 下载链接&#xff1a;https://pan.baidu.com/s/18ukDs6yL64qU6thYyZEo-Q?pwdo8he 提取码&#xff1a;o8he 一路傻瓜安装&#xff0c;安装后点击继续试用 Ubuntu系统下载 这里我使用的是官网的22.04版本&#xff0c;由于大于4G&#xff0c;无法上传至百度网盘…...

Linux下的CGI服务器

一、概述 使用进程池&#xff0c;半同步/半异步并发模式。 同步进程&#xff1a;工作子进程负责进行具体的连接以及具体的I/O&#xff0c;顺序执行 异步进程&#xff1a;主进程监听连接事件&#xff0c;将连接任务分发给子线程 二、设计逻辑 1.设计进程池的创建逻辑 2.父…...

后端开发3.Fastdfs的搭建

使用Docker安装 拉取镜像 docker pull registry.cn-beijing.aliyuncs.com/tianzuo/fastdfs 启动容器(修改ip)【fastdfs/自启动】(22122/23000/8888) docker run -d --restart=always --privileged=true --net=host --name=fastdfs -e IP=你的ip地址 -e WEB_PORT=8888 -v …...

目标检测与跟踪 (3)- TensorRTYOLO V8性能优化与部署测试

系列文章目录 目标检测与跟踪 &#xff08;1&#xff09;- 机器人视觉与YOLO V8_Techblog of HaoWANG的博客-CSDN博客 目标检测与跟踪 &#xff08;2&#xff09;- YOLO V8配置与测试_Techblog of HaoWANG的博客-CSDN博客 目录 系列文章目录 前言 YOLO v8 TensorRT 一、…...

SAS-数据集SQL垂直(纵向)合并

一、SQL垂直合并的基本语法 一个selectt对应一个表&#xff0c;select之间用set-operator连接&#xff0c;set-operator包括&#xff1a;except&#xff08;期望&#xff09;、intersect&#xff08;相交&#xff09;、union&#xff08;合并&#xff09;&#xff0c;outer un…...

SpringBoot3 整合Prometheus + Grafana

通过Prometheus Grafana对线上应用进行观测、监控、预警… 健康状况【组件状态、存活状态】Health运行指标【cpu、内存、垃圾回收、吞吐量、响应成功率…】Metrics… 1. SpringBoot Actuator 1. 基本使用 1. 场景引入 <dependency><groupId>org.springframew…...

Python实现GA遗传算法优化LightGBM回归模型(LGBMRegressor算法)项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档视频讲解&#xff09;&#xff0c;如需数据代码文档视频讲解可以直接到文章最后获取。 1.项目背景 遗传算法&#xff08;Genetic Algorithm&#xff0c;GA&#xff09;最早是由美国的 John holland于20世…...

【基于IDEA + Spark 3.4.1 + sbt 1.9.3 + Spark MLlib 构建逻辑回归鸢尾花分类预测模型】

逻辑回归进行鸢尾花分类的案例 背景说明&#xff1a; 基于IDEA Spark 3.4.1 sbt 1.9.3 Spark MLlib 构建逻辑回归鸢尾花分类预测模型&#xff0c;这是一个分类模型案例&#xff0c;通过该案例&#xff0c;可以快速了解Spark MLlib分类预测模型的使用方法。 依赖 ThisBui…...

资深测试老鸟整理,性能测试-常见调优详细,卷起来...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 常见的一些性能缺…...

【第五章 flutter学习之flutter进阶组件-上篇】

文章目录 一、列表组件1.常规列表2.动态列表 二、FridView组件三、Stack层叠组件四、AspectRatio Card CircleAvatar组件五、按钮组件六、Stack组件七、Wrap组件八、StatefulWidget有状态组件总结 一、列表组件 1.常规列表 children: const <Widget>[ListTile(leading: …...

鸿蒙边缘计算网关正式开售

IDO-IPC3528鸿蒙边缘计算网关基于RK3568研发设计&#xff0c;采用22nm先进工艺制程&#xff0c;四核A55 CPU&#xff0c;主频高达2.0GHz&#xff0c;支持高达8GB高速LPDDR4&#xff0c;1T算力NPU&#xff0c;4K H.265/H264硬解码&#xff1b;视频输出接口HDMI2.0&#xff0c;双…...

Bytebase 2.5.0 - VCS 集成支持 Azure DevOps,支持达梦数据库

&#x1f680; 新功能 VCS 集成支持 Azure DevOps。研发版本支持达梦数据库。允许用户设置需要重新登录的频率。支持选择并导出数据库变更历史。新增 MySQL Schema 设计器。支持字段模板库。 &#x1f384; 改进 在 SQL 编辑器中&#xff0c;优化 MongoDB 的查询结果。优化 …...

tomcat通过systemctl启动时报错Cannot find /usr/local/tomcat/bin/setclasspath.sh

解决方法&#xff0c;检查自己的CATALINA_HOME和TOMCAT_HOME配置情况 我的配置在/etc/profile下的如下 使其立即生效 后将/usr/lib/systemd/system/tomcat.service中的CATALINA_HOME和TOMCAT_HOME和/etc/profile改一致 重新加载再重启解决 解决方法&#xff0c;检查自己的C…...

Django架构图

1. Django 简介 基本介绍 Django 是一个由 Python 编写的一个开放源代码的 Web 应用框架 使用 Django&#xff0c;只要很少的代码&#xff0c;Python 的程序开发人员就可以轻松地完成一个正式网站所需要的大部分内容&#xff0c;并进一步开发出全功能的 Web 服务 Django 本身…...

vue- 创建wms-web项目

vue 发展历程 安装vite 第一步 创建wms-web项目 第二步 打开文件夹并安装所有开发环境的依赖 都可以放静态资源 public>vite.svg 不会重新编译成其他名字 assets>vue.svg 会重新编译成一个随机的名称 重新编译 启动 第三步 spa 单页渲染 第四步 安装路由 第五步 …...

集成学习:机器学习模型如何“博采众长”

前置概念 偏差 指模型的预测值与真实值之间的差异&#xff0c;它反映了模型的拟合能力。 方差 指模型在不同的训练集上产生的预测结果的差异&#xff0c;它反映了模型的稳定性。 方差和偏差对预测结果所造成的影响 在机器学习中&#xff0c;我们通常希望模型的偏差和方差都…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...