第二部分 基础算法——C++一本通:第四章 递归算法:1204:爬楼梯(讲解)
2021/12/19 20:54:19
本文主要是介绍第二部分 基础算法——C++一本通:第四章 递归算法:1204:爬楼梯(讲解),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1204:爬楼梯 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 18652 通过数: 9894 【题目描述】 树老师爬楼梯,他可以每次走1级或者2级,输入楼梯的级数,求不同的走法数。 例如:楼梯一共有3级,他可以每次都走一级,或者第一次走一级,第二次走两级,也可以第一次走两级,第二次走一级,一共3种方法。 【输入】 输入包含若干行,每行包含一个正整数N,代表楼梯级数,1≤N≤30。 【输出】 不同的走法数,每一行输入对应一行输出。 【输入样例】 5 8 10 【输出样例】 8 34 89
本题是要使用递归的,但是,要先知道递归的特征。
递归的特征是一个问题的求解需要一系列的计算,这一系列的计算存在着某种关联。
所以,我们要先找到关联。
关联如下:
/*1 台阶数 1 方法数 2 台阶数 11 2 方法数 3 111 12 21 4 1111 112 121 211 22 5 11111 1112 1121 1211 2111 221 212 122 */
可得1=1
2=2
3=3
4=5
5=8
就可以算出关联是:n=(n-1)+(n-2)
第3项方法数=第2项方法数+第1项方法数;
所以我们先定义
long long a[50],i,n;
a[50]是因为题目说楼梯数,虽然只说30,但保险起见,定大一点。
然后输入n,就是台阶数。再将台阶1和台阶2另外处理;
cin>>n; a[1]=1; a[2]=2;
之后就从台阶3开始算,并带入关联式:
for(i=3;i<=n;i++){ a[i]=a[i-1]+a[i-2]; }
最后再输出a [ n ]就好了,至于输入若干行就你们自己打吧,思路已经说了。
这篇关于第二部分 基础算法——C++一本通:第四章 递归算法:1204:爬楼梯(讲解)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升