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

青蛙跳台阶问题

请添加图片描述
本期介绍🍖
主要介绍:青蛙跳台阶问题,青蛙跳台阶与斐波那契数列的关系👀。


文章目录

  • 1. 题目
  • 2. 递归解题思路
  • 3. 迭代解题思路


1. 题目

  从前有一只青蛙他想跳台阶,有n级台阶,青蛙一次可以跳1级台阶,也可以跳2级台阶;问:该青蛙跳到第n级台阶一共有多少种跳法。


2. 递归解题思路

  当这只青蛙跳上了第n级台阶,它只可能是从(n-2)级或(n-1)级台阶跳上第n级台阶的,因为这只青蛙每次要么跳1级台阶,要么2级台阶。假设通过跳上第(n-2)级台阶有StepJump(n-2)种跳法,第(n-1)级台阶有StepJump(n-1)种跳法。那么青蛙从第(n-2)级台阶跳上第n级台阶就有StepJump(n-2)种跳法,同理青蛙从第(n-1)级台阶跳上第n级台阶就有StepJump(n-1)种跳法,那么必然可以得到:StepJump(n) = StepJump(n-1) + StepJump(n-2),如下图所示:

在这里插入图片描述

  照这样演化下去,跳上某级台阶的跳法等于前两级台阶跳法的和。如此往下递推,直到计算跳上第1级台阶和第2级台阶的跳法,如下图所示。青蛙跳上1级台阶只有一种跳法,跳上2级台阶有2种跳法,以此作为递归函数的限制条件。

在这里插入图片描述
  代码如下:

#include<stdio.h>int StepJump(int n)
{if (n == 1){return 1;}else if (n == 2){return 2;}else{return StepJump(n - 1) + StepJump(n - 2);}
}int main()
{int n = 0;//需要跳的台阶数while (scanf("%d", &n) == 1){int back = StepJump(n);printf("跳上第%d级台阶有>:%d种跳法\n", n, back);}return 0;
}

在这里插入图片描述


3. 迭代解题思路

  青蛙跳台阶特点:跳上某级台阶的跳法等于前两级台阶跳法的和,斐波那契数列的特点:每一项等于前两项之和。大家会惊讶的发现,青蛙跳平台问题的本质就是斐波那契额数列的运算。
  通过求斐波那契数那一章学习,会得知使用递归实现求斐波那契数,会导致过多的冗余计算,效率过于低下。所以不妨使用迭代的思路来解决青蛙跳台阶问题,跳上1级台阶有1种跳法,跳上两级台阶有3种跳法。从第3级台阶开始往后,每级台阶都是前两级台阶跳法的和。实现代码如下:

#include<stdio.h>int StepJump(int n)
{int first = 1;int second = 1;int sum = 1;while (n >= 2){sum = first + second;first = second;second = sum;n--;}return sum;
}int main()
{int n = 0;while (scanf("%d", &n) == 1){int back = StepJump(n);printf("跳上第%d级台阶有>:%d种跳法\n", n, back);}return 0;
}

在这里插入图片描述


在这里插入图片描述

这份博客👍如果对你有帮助,给博主一个免费的点赞以示鼓励欢迎各位🔎点赞👍评论收藏⭐️,谢谢!!!
如果有什么疑问或不同的见解,欢迎评论区留言欧👀。

相关文章:

青蛙跳台阶问题

本期介绍&#x1f356; 主要介绍&#xff1a;青蛙跳台阶问题&#xff0c;青蛙跳台阶与斐波那契数列的关系&#x1f440;。 文章目录 1. 题目2. 递归解题思路3. 迭代解题思路 1. 题目 从前有一只青蛙他想跳台阶&#xff0c;有n级台阶&#xff0c;青蛙一次可以跳1级台阶&#xff…...

linux日常运维2

下载linux离线安装包---- 利用 Downloadonly 插件下载 RPM 软件包及其所有依赖包 1. 先找个可以上网的linux操作系统&#xff0c;这里是以centos7操作系统为例&#xff0c;如果要使用centos6就先安装一个centos6的系统&#xff0c;然后让他可以上网&#xff0c;后面步骤如下 a.…...

flink cdc mysql整理与总结

文章目录 一、业务中常见的需要数据同步的场景CDC是什么FlinkCDC是什么CDC原理为什么是FlinkCDC业务场景flink cdc对应flink的版本 二、模拟案例1.阿里云flink sql2.开源flink sql(单机模式)flink 安装安装mysql3.flink datastream 三、总结 提示&#xff1a;以下是本篇文章正文…...

【三维重建】ePnP

PnP问题应用与一下场景&#xff1a; 已知三维点和对应二维点以及相机相机内参数&#xff0c;可以获取相机外参。 我们介绍其中的一种算法&#xff1a;ePnP 算法流程 1、ePnP算法首先在世界坐标系内寻找4个控制点&#xff0c;记作 C 1 w , C 2 w , C 3 w , C 4 w C_1^w,C_2^w,…...

C++进阶之路:何为运算符重载、赋值运算符重载与前后置++重载(类与对象_中篇)

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…...

8、python基础知识图谱

...

智慧校园建设规划方案

在信息化浪潮的推动下&#xff0c;智慧校园的建设已成为教育现代化的必然趋势。以创新科技赋能教育&#xff0c;打造智慧校园&#xff0c;旨在提升教学品质&#xff0c;优化管理流程&#xff0c;增强学生体验。构建智慧校园需要具有前瞻性的规划方案&#xff0c;它将以教育为核…...

【深度学习实战—8】:基于MediaPipe的人脸检测

✨博客主页&#xff1a;王乐予&#x1f388; ✨年轻人要&#xff1a;Living for the moment&#xff08;活在当下&#xff09;&#xff01;&#x1f4aa; &#x1f3c6;推荐专栏&#xff1a;【图像处理】【千锤百炼Python】【深度学习】【排序算法】 目录 &#x1f63a;一、Med…...

OSCP学习,布置你的Kali Linux

为什么要写这篇文章&#xff1f; 我是一个OSCP学习者&#xff0c;以教促学。同时也能让各位入门的师傅们更好的了解OSCP这门课程。本人文笔不太好&#xff0c;如果有什么写的不对的地方&#xff0c;师傅们多多指正。 参考资料&#xff1a; OSCP 考试电子书 Linux Basics for…...

PWA离线优先策略:提升用户体验的关键步骤

Progressive Web Apps (PWA) 的离线优先策略是通过Service Worker和Cache API实现的&#xff0c;它允许在没有网络连接时仍然可以访问网站的部分或全部内容。 2500G计算机入门到高级架构师开发资料超级大礼包免费送&#xff01; 1. 创建Service Worker注册文件&#xff08;se…...

网页提示“非私密连接”是为什么?

网页提示“非私密连接”&#xff08;英文提示可能是 "Your connection is not private" 或 "Your connection is not secure"&#xff09;主要是因为浏览器无法验证你正试图访问的网站的SSL/TLS证书&#xff0c;或者是证书存在问题&#xff0c;从而无法建立…...

[自动驾驶技术]-8 Tesla自动驾驶方案之硬件(AI Day 2022)

特斯拉在AI Day 2022先介绍了AI编译器&#xff0c;后面又介绍了Dojo的硬件软件&#xff0c;软件部分和AI编译器有部分重叠&#xff0c;本文介绍还是延用AI Day的思路&#xff0c;分为三部分&#xff1a;AI编译和推理&#xff0c;Dojo硬件&#xff0c;Dojo软件。 特斯拉车道检测…...

人力资源管理信息化系统如何支持企业开展管理诊断?

华恒智信人力资源顾问有限公司致力于帮助企业开展人力资源管理方面的各项提升改进工作&#xff0c;在长期的咨询工作中&#xff0c;最常听到企业提到的问题莫过于管理诊断方面的问题&#xff0c;事实上&#xff0c;很多企业在日常工作中&#xff0c;都意识到企业内部存在管理方…...

Cohere继Command-R+之后发布大模型Aya-23,性能超越 Gemma、Mistral 等,支持中文

前言 近年来&#xff0c;多语言大模型&#xff08;MLLM&#xff09;发展迅速&#xff0c;但大多数模型的性能依然存在显著差距&#xff0c;尤其是在非英语语言方面表现不佳。为了推动多语言自然语言处理技术的发展&#xff0c;Cohere团队发布了新的多语言指令微调模型家族——…...

身为UI设计老鸟,不学点3D,好像要被潮流抛弃啦,卷起来吧。

当前3D原则在UI设计中运用的越来越多&#xff0c;在UI设计中&#xff0c;使用3D元素可以为界面带来以下几个价值&#xff1a; 增强视觉冲击力&#xff1a;3D元素可以通过立体感和逼真的效果&#xff0c;为界面增添视觉冲击力&#xff0c;使得设计更加生动、吸引人&#xff0c;并…...

线代-向量eg3.1 3.2 3.4

...

【C语言】实现贪吃蛇--项目实践(超详细)

前言&#xff1a; 贪吃蛇游戏大家都玩过吧&#xff1f;这次我们要用C语言来亲手制作一个&#xff01;这个项目不仅能让我们复习C语言的知识&#xff0c;还能了解游戏是怎么一步步做出来的。我们会一起完成蛇的移动、食物的生成&#xff0c;还有碰撞检测等有趣的部分。准备好了…...

Elasticsearch 分析器的高级用法一(同义词,高亮搜索)

Elasticsearch 分析器的高级用法一&#xff08;同义词&#xff0c;高亮搜索&#xff09; 同义词简介分析使用同义词案例 高亮搜索高亮搜索策略unifiedplainvh 同义词 简介 在搜索场景中&#xff0c;同义词用来处理不同的查询词&#xff0c;有可能是想表达相同的搜索目标。 例…...

Python 开心消消乐

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…...

mysql - 索引基本知识梳理

mysql索引基本知识梳理 索引介绍 官方介绍索引是帮助MySQL高效获取数据的数据结构, 原理为以空间换时间, mysql的索引采用的是B树的结构 索引的优缺点 优点&#xff1a; 提高查询效率降低数据库IO成本通过索引对数据进行排序, 降低排序成本, 降低CPU消耗 缺点&#xff1a…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...

aardio 自动识别验证码输入

技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”&#xff0c;于是尝试整合图像识别与网页自动化技术&#xff0c;完成了这套模拟登录流程。核心思路是&#xff1a;截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...