目录
C++登山爬石梯
一、题目要求
1、编程实现
2、输入输出
二、算法分析
三、程序编写
四、程序说明
五、运行结果
六、考点分析
七、推荐资料
C++登山爬石梯
一、题目要求
1、编程实现
小明周末和朋友约好了一起去爬山，来到山下，发现登山道是由石头铺成，每一段会有向上铺的石阶，然后是一段平路，如此反复，直到山顶。刚好最近在学c++编程，就想到小兔子老师课堂上讲的爬楼梯的例子，想实现每一段向上的石阶走上去有多少种方法。
每次可以爬 1 或 2 个台阶，走到这段石阶最上面会有多少种不同的走法呢？；让我们来帮小明实现一下吧！（注：到达石阶最上面的阶梯数量由键盘输入且是一个正整数）
2、输入输出
输入描述：只有一行，到达山顶的阶梯数n，1<=n<=40
输出描述：只有一行，一个整数，即到达石阶最上面的方法数
输入样例：
2输出样例：
2解释：到达第2个阶梯，有2种方法：1个台阶+1个台阶和2个台阶
二、算法分析
- 从给定题目的初步分析可以看出，这是比较经典的爬楼梯问题
- 我们先分析一下这个题目
- 到达第1个台阶是只有1种方法：1个
- 到达第2个台阶有2种方法：1个+1个和2个
- 到达第3个台阶有3种方法：1个+1个+1个，1个+2个和2个加1个
- 到达第4个台阶有5种方法：1个+1个+1个+1个，1个+1个+2个，1个+2个+1个，2个+1个+1个和2个+2个
- 根据上面就可以找到规律，第n个台阶的方法数量等于前1个和前2个的方法数量之和
- 所以解决这个问题的方法就有多种，这里采用最常用的递归思路和动态规划思路进行实现
三、程序编写
四、程序说明
- 首先需要导入输入输出流头文件
- 接着再次导入输入输出流格式控制头文件
- 然后是引入std命名空间中的所有成员到当前的程序中，这样在当前的程序中就可以直接使用 std 命名空间中的所有成员，而不需要使用的时候在成员前面加上（std::）前缀
- ===========递归===========
- 定义递归函数，并将n作为参数传入
- 如果n=1就返回1，n=2返回2
- 否则就再次调用自己并返回：将n-1和n-2作为参数传入进行求和
- ===========动态规划===========
- 声明一个数组（数组大小比题目要求的大一点），用来存放第i个台阶对应的方法数
- 小朋友们学的多一点可以使用动态数组vector实现较好
- 接着给数组的第一项和第二项进行赋值
- 然后利用for循环从第三项开始逐个遍历直到第n项
- 将状态转移方程设置为第i项等于第i-1项加上第i-2项
- 最后返回数组的第n项
- =============================
- 接着声明程序的入口，也就是主函数（主函数在一个程序中只允许出现一次）
- 根据题目要求声明一个整形变量n
- 然后利用输入流对象cin，从键盘读取这个变量的值
- 最后利用输出流对象cout，输出调用函数即可
- 最后返回0，程序结束
本文作者：小兔子编程 作者首页：https://blog.csdn.net/frank2102
五、运行结果
2
24
5六、考点分析
难度级别：一般，这题相对而言在于题目的分析，具体主要考查如下：
- 分析题目 找到相应的解题思路
- 充分掌握变量、数组的定义和使用
- 学会递归算法的思路原理及相应的应用
- 学会动态规划算法的思路原理及相应的应用
- 学会输入流对象cin的使用，从键盘读入相应的数据
- 学会for循环的使用，在确定循环次数的时候推荐使用学会
- 学会if条件判断语句的使用，满足一定条件才能执行后面的语句
- 学会if...else...双分支语句的使用，条件满足执行一种处理，不满足执行另一种处理
- 掌握输出流对象cout的使用，与流插入运算符 << 结合使用将对象输出到终端显示
- 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路
- 充分掌握数组定义和使用、分支语句、循环语句和递归和动态规划算法知识的使用
PS：方式方法有多种，小朋友们只要能够达到题目要求即可！
七、推荐资料
- 所有考级比赛学习相关资料合集【推荐收藏】
