首页/新闻资讯/正文详情

使用递归解决爬楼梯方法数问题

发布时间:2026/9/24 21:28:19 来源:云帆数科 栏目:资讯中心
使用递归解决爬楼梯方法数问题
给定一道题假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶总共有多少种不同的方法当 n 很大时我们很难一眼猜出数量。我们不妨把 n 设定成很小的值来看。n1 时只有爬一步这一种方法方法数为 1n2 时可以爬两次一步也可以一次爬两步方法数为 2n3 时可以爬三次一步也可以爬一次一步再爬一次两步反过来爬一次两步再爬一次一步方法数为 3此时我们发现312这是否表明台阶为 n 时其方法数与台阶为 n-1、n-2 的方法数有相加关系呢多探索一层n4时爬4次一步爬2次两步爬2次一步 1次2步爬1次两步 2次一步爬1次一步1次两步再爬1次一步方法数为5532符合我们的假设式F(n)F(n-1)F(n-2); 注F(n)表示台阶为n时的方法数为了更直观地理解这个递推关系我们以 F(5) 为例画出它的递归调用树。每个节点代表一次方法调用节点下方的数字表示该子问题的结果flowchart TD F5[F(5) 5] F4[F(4) 3] F3a[F(3) 2] F3b[F(3) 2] F2a[F(2) 2] F1a[F(1) 1] F2b[F(2) 2] F1b[F(1) 1] F2c[F(2) 2] F1c[F(1) 1] F5 -- F4 F5 -- F3a F4 -- F3b F4 -- F2a F3a -- F2b F3a -- F1a F3b -- F2c F3b -- F1b F2a -- F1c从图中可以看到F(5) 会先拆分成 F(4) 和 F(3)而 F(4) 又继续拆分成 F(3) 和 F(2)F(3) 再拆分成 F(2) 和 F(1)。当拆分到 F(1) 和 F(2) 这两个已知结果时递归停止然后逐层向上返回最终得到 F(5) F(4) F(3) 3 2 5。为什么会有这个等式呢我们来做一次抽象假设n很大大到了100。要想得知此时的方法数我们设想要想踏上第100阶那么上一步应该在哪显然第97阶不能不能一步跳三阶到达100只剩下98 和 99 两阶一个可以爬1次两步到达一个可以爬1次一步到达。那么推理可得n100的总方法数应该是n98和n99的方法数相加因为这两阶都只有一个方法到达100此时我们宣布算出来了就是这两个相加至于这两个数是多少我们算n100的人并不关心应该交由算n99和n98的人来得出。他们在计算时也能轻易得出F(99)F(98)F(97);F(98)F(97)F(96)。而依旧把更小的n交由他人计算以此类推直到n1和n2我们惊喜的发现这两个我们一开始就知道了分别等于1 和 2。将其步步往上提交返回我们最终能算出来最终的结果。这就是递归的核心思想将一个大的问题拆分成无数小的问题往下调取直至获取到最小的不可计算想返回。现在我们编写一个可以执行的方法public long F(int n){ if(n1){ return 1; } else if(n 2){ return 2; } else{ return F(n-1)F(n-2); } }该方法接收int n;假如n1或2时能直接返回。当没有可直接返回时会返回F(n-1)F(n-2);执行时会继续调用F方法进行计算直至返回1或2。该方法能做到较小n时的快速返回但由于没有进行优化不建议输入较大值。n每增加1所要执行的子方法几乎要翻一倍。

相关推荐

Jmeter提取器实战:正则与JSON提取器实现接口数据关联
Jmeter提取器实战:正则与JSON提取器实现接口数据关联

刚入行做接口测试的时候,我卡得最久的不是怎么发请求,而是怎么把上一个接口返回的数据传给下一个接口。登录接口返回了一个token,下一个接口必须带着这个token才能访问,我当时的做法是手动复制粘贴到请求头里。单个接口这么干没问… · 2026/9/24 21:28:07

移动搜索查询处理优化:短查询、意图识别与改写策略实战
移动搜索查询处理优化:短查询、意图识别与改写策略实战

1. 移动搜索的查询处理到底难在哪移动搜索和桌面搜索看起来只是屏幕大小不一样,但真正做过搜索链路的人都知道,查询处理这一层在移动端几乎是另一套逻辑。桌面端用户输入长尾词的比例高,有耐心翻页、改词、加筛选条件;移动端用户平… · 2026/9/24 21:28:07

Unity GC卡顿优化实战:从原理到降分配方案
Unity GC卡顿优化实战:从原理到降分配方案

做了几年 Unity 项目,最让人抓狂的从来不是“明显的卡顿”,而是那种“一切看起来都正常,但一进战斗就偶然顿一下”的幽灵式掉帧。我自己就遇到过:战斗逻辑不复杂、场景面数不高、DrawCall 也能压住,可老机型上每隔十几… · 2026/9/24 21:28:07

learn-harness-engineering 的 CLAUDE.md 模板:为长期 Agent 任务设计的会话契约与操作规范
learn-harness-engineering 的 CLAUDE.md 模板:为长期 Agent 任务设计的会话契约与操作规范

【免费下载链接】learn-harness-engineering Harness engineering beginner tutorial, from 0 to 1 项目地址: https://gitcode.com/gh_mirrors/le/learn-harness-engineering 点击查看 免费下载 导读 本文以开源仓库 learn-harness-engineering 中韩文资源库 doc… · 2026/9/24 22:01:39

AI重塑身份安全底座:2026年五大趋势与落地实践
AI重塑身份安全底座:2026年五大趋势与落地实践

干安全这一行,最怕听到的一句话就是“身份系统又不是线上业务,先放放”。可你要是翻过一阵子SRC平台上的漏洞报告,或者复盘过几起影响比较大的数据泄露事件,就会得出一个扎心的结论:八成以上的攻击路径,绕到… · 2026/9/24 22:01:33

Java毕设电商平台全解析:技术架构、运行流程与答辩避坑
Java毕设电商平台全解析:技术架构、运行流程与答辩避坑

Java毕设最头疼的莫过于选方向、搭框架、写代码、调环境这一整套流程。我最近正好在帮几个学弟学妹复盘他们的毕业设计,其中“Java清城电商平台”这个项目被提到的频率非常高。如果你正在找计算机毕业设计的方向,或者手里已经有一套类似的电商系统源码但… · 2026/9/24 22:01:33

Spring Boot + Vue + 微信小程序:健身房预约管理系统架构与并发实践
Spring Boot + Vue + 微信小程序:健身房预约管理系统架构与并发实践

做健身房管理系统的人和做电商系统的朋友聊天时,经常会被问同一个问题:你们这系统不就是个预约工具吗?我的回答是:预约只是表面,真正麻烦的是预约前后那一大堆状态流转和人员权限。我做的"康益"健身房助手就… · 2026/9/24 22:01:33

Argos Translate 完全指南:如何快速搭建本地离线多语言互译
Argos Translate 完全指南:如何快速搭建本地离线多语言互译

Argos Translate 完全指南:如何快速搭建本地离线多语言互译 【免费下载链接】argos-translate Open-source offline translation library written in Python 项目地址: https://gitcode.com/GitHub_Trending/ar/argos-translate 出差到信号差的山区、处理不想… · 2026/9/24 22:01:33

OpenClaw傻瓜版安装指南:从零开始部署你的AI Agent并接入飞书
OpenClaw傻瓜版安装指南:从零开始部署你的AI Agent并接入飞书

1. 先搞清楚:OpenClaw到底是用来干嘛的,为什么能火到17万人围观 1.1 它就是一个能自己“动手干活”的开源Agent 先别急着管“傻瓜版”怎么装,得先弄明白OpenClaw是什么。很多人围观它,是因为它和那种只在网页里聊天的AI不一样——… · 2026/9/24 22:01:33

基于YOLOv8的渔船作业监控系统:从环境搭建到边缘部署全流程
基于YOLOv8的渔船作业监控系统:从环境搭建到边缘部署全流程

简介:这是一套面向计算机、人工智能、自动化等专业学生与教师的毕业设计级项目资源,围绕YOLOv8实现渔船作业监控系统,可用于毕设、课程设计、大作业或项目立项演示。压缩包共97个文件,约24.21MB,以70个Python源码文件为… · 2026/9/24 0:00:13

1D-CNN时间序列建模实战:从Conv1d原理到工业落地
1D-CNN时间序列建模实战:从Conv1d原理到工业落地

简介:面向时间序列数据建模的一维卷积神经网络完整实现,适合深度学习入门者及需要快速验证时序模型的研究者,能够从音频、文本、传感器或股价等序列中挖掘局部特征与时间依赖。压缩包体积很小,只有3KB,内含3个Python脚… · 2026/9/24 0:00:26

柔软的L:汉语语流中被忽视的舌肌张力控制
柔软的L:汉语语流中被忽视的舌肌张力控制

1. 这个“L”不是字母表里的L,而是舌尖上的L最近在几个方言群和语音教学社群里,反复看到有人发一句:“也说字母L:柔软的长舌”。初看以为是英语发音课笔记,点开才发现全是方言爱好者、播音系学生、语言康复师甚至戏曲演… · 2026/9/24 0:00:44

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码