AcWing 5933:爬楼梯 ← 递归 / 递推 / 高精度
【题目来源】
https://www.acwing.com/problem/content/5936/
【题目描述】
树老师爬楼梯,他可以每次走 1 级或者 2 级,输入楼梯的级数,求不同的走法数。
例如:楼梯一共有 3 级,他可以每次都走一级,或者第一次走一级,第二次走两级,也可以第一次走两级,第二次走一级,一共 3 种方法。
【输入格式】
输入包含若干行,每行包含一个正整数 N,代表楼梯级数。
【输出格式】
不同的走法数,每一行输入对应一行输出。
【数据范围】
单个输入最多包含 30 组数据。
1≤N≤30。
【输入样例】
5
8
10
【输出样例】
8
34
89
【算法分析】
● 递归:https://oi-wiki.org/basic/divide-and-conquer/
递归的基本思想是某个函数直接或者间接地调用自身,这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题,而不需要过分关注这个子问题是如何被解决的。
明白递归函数的作用并相信它能完成这个任务,千万不要跳进这个函数里面企图探究更多细节, 否则就会陷入无穷的细节无法自拔。
● 递推
递推法(recurrence method)是一种根据递推关系进行问题求解的方法,也是一种重要的数学方法,常用来进行序列计算。递推法能够将复杂的运算化解为若干重复的简单运算,充分发挥了计算机擅长重复处理的特点。
递推法通过初始条件,根据递推关系式,按照一定的规律逐项进行计算,直至得到结果。递推法有正推和逆推两种形式。无论正推还是逆推,关键都是要找到递推关系式。
● 高精度:https://blog.csdn.net/hnjzsyjyj/article/details/144703201
本题中 N≤30,问题规模较小,可以不用高精度。
但洛谷 P1255(https://www.luogu.com.cn/problem/P1255)与本题相比,除了 N 很大外极其类似,且需要用高精度。故用高精度也实现了一下此题。
【算法代码一:递归】
#include <bits/stdc++.h>
using namespace std;int f(int x) {if(x==0 || x==1) return 1;return f(x-1)+f(x-2);
}int main() {int n;while(cin>>n) {cout<<f(n)<<endl;}
}
【算法代码二:递推】
#include <bits/stdc++.h>
using namespace std;const int maxn=35;
int f[maxn];
int n;int main() {f[0]=1,f[1]=1;for(int i=2; i<=maxn; i++) {f[i]=f[i-1]+f[i-2];}while(cin>>n) {cout<<f[n]<<endl;}
}
【算法代码三:高精度】
#include <bits/stdc++.h>
using namespace std;string hiAdd(string a,string b) {string c;int t=0;int i=a.size()-1,j=b.size()-1;while(i>=0 || j>=0) {if(i>=0) t=(a[i]-'0')+t;if(j>=0) t+=(b[j]-'0');c+=(t%10+'0');t/=10;i--,j--;}if(t!=0) c+=(t+'0');reverse(c.begin(),c.end());return c;
}int main() {int n;while(cin>>n){string f[n+5];f[0]=f[1]="1";for(int i=2; i<=n; i++) {f[i]=hiAdd(f[i-1], f[i-2]);}cout<<f[n]<<endl;}return 0;
}/*
in:
4out:
5
*/
【参考文献】
https://www.acwing.com/solution/content/253657/
https://www.acwing.com/solution/content/254309/
相关文章:
AcWing 5933:爬楼梯 ← 递归 / 递推 / 高精度
【题目来源】 https://www.acwing.com/problem/content/5936/ 【题目描述】 树老师爬楼梯,他可以每次走 1 级或者 2 级,输入楼梯的级数,求不同的走法数。 例如:楼梯一共有 3 级,他可以每次都走一级,或者第…...
c++ 中的容器 vector 与数组 array
当初自学 c 与 c 语言时,一直被指针弄的云里雾里。后来 c 中引入了容器,避免了指针。但是,一些教材把容器的章节放在书本中后面的章节,太不合理。应该把这种方便的功能放到前面,这样一些初学者就不会遇到太多生硬难懂的…...
我的世界1.20.1forge模组开发进阶物品(7)——具有动画、3D立体效果的物品
基础的物品大家都会做了对吧?包括武器的释放技能,这次来点难度,让物品的贴图呈现动画效果和扔出后显示3D立体效果,这个3D立体效果需要先学习blockbench,学习如何制作贴图。 Blockbench Blockbench是一个用于创建和编辑三维模型的免费软件,特别适用于Minecraft模型的设计…...
ubuntu22.04安装docker engine
在Ubuntu 22.04上安装Docker Engine可以通过以下步骤完成: 更新系统包索引: sudo apt update安装必要的依赖包: 这些包允许apt通过HTTPS使用仓库。 sudo apt install -y apt-transport-https ca-certificates curl software-properties-commo…...
性能测试测试策略制定|知名软件测评机构经验分享
随着互联网产品的普及,产品面对的用户量级也越来越大,能抗住指数级增长的瞬间访问量以及交易量是保障购物体验是否顺畅的至关重要的一环,而我们的性能测试恰恰也是为此而存在的。 性能测试是什么呢?性能测试要怎么测呢?…...
Let‘s Encrypt免费证书的应用示例
文章目录 前言证书申请证书介绍cert.pemchain.pemfullchain.pemprivkey.pem 使用步骤搭建简易demo应用新建nginx配置文件测试SSL是否生效 总结 前言 最近在搞苹果应用上架的问题,据说用HTTP会被拒,但貌似不绝对,2017年苹果曾发公告说必须要求…...
threeJS——安装以及三要素
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、安装二、三要素1.场景1.1创建场景1.2向场景添加元素1.3场景属性 2.相机2.1相机特点2.2正交相机2.3空间布局2.4小姐操作 3.渲染器 总结 前言 本章简单介绍前…...
【Electron入门】进程环境和隔离
目录 一、主进程和渲染进程 1、主进程(main) 2、渲染进程(renderer) 二、预加载脚本 三、沙盒化 为单个进程禁用沙盒 全局启用沙盒 四、环境访问权限控制:contextIsolation和nodeIntegration 1、contextIsola…...
提示词框架介绍和使用场景
框架介绍 CO-STAR 框架 定义 CO-STAR是六个关键要素的缩写,每个字母代表一个特定的部分: Context(上下文) :提供任务的背景信息或环境 当前任务是为一家科技公司撰写一篇关于人工智能发展趋势的文章/ 需要为一场面向高中生的科普讲座准备内容Objective(目标) :明确任…...
牛客NC288803 和+和
import java.util.Comparator;import java.util.PriorityQueue;import java.util.Scanner;public class Main {public static void main(String[] args) {// 创建Scanner对象用于读取输入Scanner sc new Scanner(System.in);// 读取两个整数n和m,分别表示数组的…...
AI学习第七天
数组:基础概念、存储特性及力扣实战应用 在计算机科学与数学的广袤领域中,数组作为一种极为重要的数据结构,发挥着不可或缺的作用。它就像一个有序的 “数据仓库”,能高效地存储和管理大量数据。接下来,让我们深入了解…...
【uniapp原生】实时记录接口请求延迟,并生成写入文件到安卓设备
在开发实时数据监控应用时,记录接口请求的延迟对于性能分析和用户体验优化至关重要。本文将基于 UniApp 框架,介绍如何实现一个实时记录接口请求延迟的功能,并深入解析相关代码的实现细节。 前期准备&必要的理解 1. 功能概述 该功能的…...
XR应用测试:探索虚拟与现实的边界
引言 随着XR(扩展现实,Extended Reality)技术的快速发展,VR(虚拟现实)、AR(增强现实)和MR(混合现实)应用逐渐渗透到游戏、教育、医疗、工业等多个领域。对于…...
算法之算法思想
算法思想 ♥算法思想知识体系详解♥ | Java 全栈知识体系 经典算法思想总结 经典算法思想总结(含LeetCode题目推荐) | JavaGuide...
mac电脑中使用无线诊断.app查看连接的Wi-Fi带宽
问题 需要检查连接到的Wi-Fi的AP硬件支持的带宽。 步骤 1.按住 Option 键,然后点击屏幕顶部的Wi-Fi图标;2.从下拉菜单中选择 “打开无线诊断”(Open Wireless Diagnostics);3.你可能会看到一个提示窗口,…...
物理竞赛中的线性代数
线性代数 1 行列式 1.1 n n n 阶行列式 定义 1.1.1:称以下的式子为一个 n n n 阶行列式: ∣ A ∣ ∣ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ a n n ∣ \begin{vmatrix}\mathbf A\end{vmatrix} \begin{vmatrix} a_{11…...
FFmpeg-chapter3-读取视频流(原理篇)
ffmpeg网站:About FFmpeg 1 库介绍 (1)libavutil是一个包含简化编程函数的库,包括随机数生成器、数据结构、数学例程、核心多媒体实用程序等等。 (2)libavcodec是一个包含音频/视频编解码器的解码器和编…...
机器视觉线阵相机分时频闪选型/机器视觉线阵相机分时频闪选型
在机器视觉系统中,线阵相机的分时频闪技术通过单次扫描切换不同光源或亮度,实现在一幅图像中捕捉多角度光照效果,从而提升缺陷检测效率并降低成本。以下是分时频闪线阵相机的选型要点及关键考量因素: 一、分时频闪技术的核心需求 多光源同步控制 分时频闪需相机支持多路光源…...
「Selenium+Python自动化从0到1②|2025浏览器操控7大核心API实战(附高效避坑模板))」
Python 自动化操作浏览器基础方法 在进行 Web 自动化测试时,操作浏览器是必不可少的环节。Python 结合 Selenium 提供了强大的浏览器操作功能,让我们能够轻松地控制浏览器执行各种任务。本文将详细介绍如何使用 Python 和 Selenium 操作浏览器的基本方法…...
矩阵系列 题解
1.洛谷 P1962 斐波那契数列 题意 大家都知道,斐波那契数列是满足如下性质的一个数列: F n { 1 ( n ≤ 2 ) F n − 1 F n − 2 ( n ≥ 3 ) F_n \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}F_{n-2} \space (n\ge 3) \end{aligned}\right. …...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
热烈祝贺埃文科技正式加入可信数据空间发展联盟
2025年4月29日,在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上,可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞,强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...
ZYNQ学习记录FPGA(一)ZYNQ简介
一、知识准备 1.一些术语,缩写和概念: 1)ZYNQ全称:ZYNQ7000 All Pgrammable SoC 2)SoC:system on chips(片上系统),对比集成电路的SoB(system on board) 3)ARM:处理器…...
篇章二 论坛系统——系统设计
目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...
41道Django高频题整理(附答案背诵版)
解释一下 Django 和 Tornado 的关系? Django和Tornado都是Python的web框架,但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架,鼓励快速开发和干净、实用的设计。它遵循MVC设计,并强调代码复用。Django有…...
标注工具核心架构分析——主窗口的图像显示
🏗️ 标注工具核心架构分析 📋 系统概述 主要有两个核心类,采用经典的 Scene-View 架构模式: 🎯 核心类结构 1. AnnotationScene (QGraphicsScene子类) 主要负责标注场景的管理和交互 🔧 关键函数&…...
