算法学习008-登山爬石梯 c++动态规划/递归算法实现 中小学算法思维学习 信奥算法解析

目录

C++登山爬石梯

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、程序说明

五、运行结果

六、考点分析

七、推荐资料

C++登山爬石梯

一、题目要求

1、编程实现

小明周末和朋友约好了一起去爬山，来到山下，发现登山道是由石头铺成，每一段会有向上铺的石阶，然后是一段平路，如此反复，直到山顶。刚好最近在学c++编程，就想到小兔子老师课堂上讲的爬楼梯的例子，想实现每一段向上的石阶走上去有多少种方法。

每次可以爬 1 或 2 个台阶，走到这段石阶最上面会有多少种不同的走法呢？；让我们来帮小明实现一下吧！（注：到达石阶最上面的阶梯数量由键盘输入且是一个正整数）

2、输入输出

输入描述：只有一行，到达山顶的阶梯数n，1<=n<=40

输出描述：只有一行，一个整数，即到达石阶最上面的方法数

输入样例：

2

输出样例：

2

解释：到达第2个阶梯，有2种方法：1个台阶+1个台阶和2个台阶

二、算法分析

1. 从给定题目的初步分析可以看出，这是比较经典的爬楼梯问题
2. 我们先分析一下这个题目
3. 到达第1个台阶是只有1种方法：1个
4. 到达第2个台阶有2种方法：1个+1个和2个
5. 到达第3个台阶有3种方法：1个+1个+1个，1个+2个和2个加1个
6. 到达第4个台阶有5种方法：1个+1个+1个+1个，1个+1个+2个，1个+2个+1个，2个+1个+1个和2个+2个
7. 根据上面就可以找到规律，第n个台阶的方法数量等于前1个和前2个的方法数量之和
8. 所以解决这个问题的方法就有多种，这里采用最常用的递归思路和动态规划思路进行实现

三、程序编写

四、程序说明

1. 首先需要导入输入输出流头文件
2. 接着再次导入输入输出流格式控制头文件
3. 然后是引入std命名空间中的所有成员到当前的程序中，这样在当前的程序中就可以直接使用 std 命名空间中的所有成员，而不需要使用的时候在成员前面加上（std::）前缀
4. ===========递归===========
5. 定义递归函数，并将n作为参数传入
6. 如果n=1就返回1，n=2返回2
7. 否则就再次调用自己并返回：将n-1和n-2作为参数传入进行求和
8. ===========动态规划===========
9. 声明一个数组（数组大小比题目要求的大一点），用来存放第i个台阶对应的方法数
10. 小朋友们学的多一点可以使用动态数组vector实现较好
11. 接着给数组的第一项和第二项进行赋值
12. 然后利用for循环从第三项开始逐个遍历直到第n项
13. 将状态转移方程设置为第i项等于第i-1项加上第i-2项
14. 最后返回数组的第n项
15. =============================
16. 接着声明程序的入口，也就是主函数（主函数在一个程序中只允许出现一次）
17. 根据题目要求声明一个整形变量n
18. 然后利用输入流对象cin，从键盘读取这个变量的值
19. 最后利用输出流对象cout，输出调用函数即可
20. 最后返回0，程序结束

 本文作者：小兔子编程 作者首页：https://blog.csdn.net/frank2102

五、运行结果

2
2

4
5

六、考点分析

难度级别：一般，这题相对而言在于题目的分析，具体主要考查如下：

1. 分析题目 找到相应的解题思路
2. 充分掌握变量、数组的定义和使用
3. 学会递归算法的思路原理及相应的应用
4. 学会动态规划算法的思路原理及相应的应用
5. 学会输入流对象cin的使用，从键盘读入相应的数据
6. 学会for循环的使用，在确定循环次数的时候推荐使用学会
7. 学会if条件判断语句的使用，满足一定条件才能执行后面的语句
8. 学会if...else...双分支语句的使用，条件满足执行一种处理，不满足执行另一种处理
9. 掌握输出流对象cout的使用，与流插入运算符 << 结合使用将对象输出到终端显示
10. 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路
11. 充分掌握数组定义和使用、分支语句、循环语句和递归和动态规划算法知识的使用

PS：方式方法有多种，小朋友们只要能够达到题目要求即可！

七、推荐资料

• 所有考级比赛学习相关资料合集【推荐收藏】