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

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/ 【题目描述】 树老师爬楼梯&#xff0c;他可以每次走 1 级或者 2 级&#xff0c;输入楼梯的级数&#xff0c;求不同的走法数。 例如&#xff1a;楼梯一共有 3 级&#xff0c;他可以每次都走一级&#xff0c;或者第…...

c++ 中的容器 vector 与数组 array

当初自学 c 与 c 语言时&#xff0c;一直被指针弄的云里雾里。后来 c 中引入了容器&#xff0c;避免了指针。但是&#xff0c;一些教材把容器的章节放在书本中后面的章节&#xff0c;太不合理。应该把这种方便的功能放到前面&#xff0c;这样一些初学者就不会遇到太多生硬难懂的…...

我的世界1.20.1forge模组开发进阶物品(7)——具有动画、3D立体效果的物品

基础的物品大家都会做了对吧?包括武器的释放技能,这次来点难度,让物品的贴图呈现动画效果和扔出后显示3D立体效果,这个3D立体效果需要先学习blockbench,学习如何制作贴图。 Blockbench Blockbench是一个用于创建和编辑三维模型的免费软件,特别适用于Minecraft模型的设计…...

ubuntu22.04安装docker engine

在Ubuntu 22.04上安装Docker Engine可以通过以下步骤完成&#xff1a; 更新系统包索引&#xff1a; sudo apt update安装必要的依赖包&#xff1a; 这些包允许apt通过HTTPS使用仓库。 sudo apt install -y apt-transport-https ca-certificates curl software-properties-commo…...

性能测试测试策略制定|知名软件测评机构经验分享

随着互联网产品的普及&#xff0c;产品面对的用户量级也越来越大&#xff0c;能抗住指数级增长的瞬间访问量以及交易量是保障购物体验是否顺畅的至关重要的一环&#xff0c;而我们的性能测试恰恰也是为此而存在的。 性能测试是什么呢&#xff1f;性能测试要怎么测呢&#xff1f…...

Let‘s Encrypt免费证书的应用示例

文章目录 前言证书申请证书介绍cert.pemchain.pemfullchain.pemprivkey.pem 使用步骤搭建简易demo应用新建nginx配置文件测试SSL是否生效 总结 前言 最近在搞苹果应用上架的问题&#xff0c;据说用HTTP会被拒&#xff0c;但貌似不绝对&#xff0c;2017年苹果曾发公告说必须要求…...

threeJS——安装以及三要素

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、安装二、三要素1.场景1.1创建场景1.2向场景添加元素1.3场景属性 2.相机2.1相机特点2.2正交相机2.3空间布局2.4小姐操作 3.渲染器 总结 前言 本章简单介绍前…...

【Electron入门】进程环境和隔离

目录 一、主进程和渲染进程 1、主进程&#xff08;main&#xff09; 2、渲染进程&#xff08;renderer&#xff09; 二、预加载脚本 三、沙盒化 为单个进程禁用沙盒 全局启用沙盒 四、环境访问权限控制&#xff1a;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&#xff0c;分别表示数组的…...

AI学习第七天

数组&#xff1a;基础概念、存储特性及力扣实战应用 在计算机科学与数学的广袤领域中&#xff0c;数组作为一种极为重要的数据结构&#xff0c;发挥着不可或缺的作用。它就像一个有序的 “数据仓库”&#xff0c;能高效地存储和管理大量数据。接下来&#xff0c;让我们深入了解…...

【uniapp原生】实时记录接口请求延迟,并生成写入文件到安卓设备

在开发实时数据监控应用时&#xff0c;记录接口请求的延迟对于性能分析和用户体验优化至关重要。本文将基于 UniApp 框架&#xff0c;介绍如何实现一个实时记录接口请求延迟的功能&#xff0c;并深入解析相关代码的实现细节。 前期准备&必要的理解 1. 功能概述 该功能的…...

XR应用测试:探索虚拟与现实的边界

引言 随着XR&#xff08;扩展现实&#xff0c;Extended Reality&#xff09;技术的快速发展&#xff0c;VR&#xff08;虚拟现实&#xff09;、AR&#xff08;增强现实&#xff09;和MR&#xff08;混合现实&#xff09;应用逐渐渗透到游戏、教育、医疗、工业等多个领域。对于…...

算法之算法思想

算法思想 ♥算法思想知识体系详解♥ | Java 全栈知识体系 经典算法思想总结 经典算法思想总结&#xff08;含LeetCode题目推荐&#xff09; | JavaGuide...

mac电脑中使用无线诊断.app查看连接的Wi-Fi带宽

问题 需要检查连接到的Wi-Fi的AP硬件支持的带宽。 步骤 1.按住 Option 键&#xff0c;然后点击屏幕顶部的Wi-Fi图标&#xff1b;2.从下拉菜单中选择 “打开无线诊断”&#xff08;Open Wireless Diagnostics&#xff09;&#xff1b;3.你可能会看到一个提示窗口&#xff0c;…...

物理竞赛中的线性代数

线性代数 1 行列式 1.1 n n n 阶行列式 定义 1.1.1&#xff1a;称以下的式子为一个 n n n 阶行列式&#xff1a; ∣ 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网站&#xff1a;About FFmpeg 1 库介绍 &#xff08;1&#xff09;libavutil是一个包含简化编程函数的库&#xff0c;包括随机数生成器、数据结构、数学例程、核心多媒体实用程序等等。 &#xff08;2&#xff09;libavcodec是一个包含音频/视频编解码器的解码器和编…...

机器视觉线阵相机分时频闪选型/机器视觉线阵相机分时频闪选型

在机器视觉系统中,线阵相机的分时频闪技术通过单次扫描切换不同光源或亮度,实现在一幅图像中捕捉多角度光照效果,从而提升缺陷检测效率并降低成本。以下是分时频闪线阵相机的选型要点及关键考量因素: 一、分时频闪技术的核心需求 多光源同步控制 分时频闪需相机支持多路光源…...

「Selenium+Python自动化从0到1②|2025浏览器操控7大核心API实战(附高效避坑模板))」

Python 自动化操作浏览器基础方法 在进行 Web 自动化测试时&#xff0c;操作浏览器是必不可少的环节。Python 结合 Selenium 提供了强大的浏览器操作功能&#xff0c;让我们能够轻松地控制浏览器执行各种任务。本文将详细介绍如何使用 Python 和 Selenium 操作浏览器的基本方法…...

矩阵系列 题解

1.洛谷 P1962 斐波那契数列 题意 大家都知道&#xff0c;斐波那契数列是满足如下性质的一个数列&#xff1a; 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. …...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

搭建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…...