当前位置: 首页 > 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…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...