转自：http://blog.csdn.net/leo115/article/details/8039962
题目：
给定一个有N个台阶的楼梯，一个人从下到上开始跳台阶，这个人有两种跳的方式：一次跳一个台阶，一次跳两个台阶；
问：从台阶底端跳到台阶顶端，有多少种跳台阶的方式？
分析：
首先我们考虑最简单的情况。如果只有1个台阶，那么显然只有一种跳法；如果 是2级台阶，那么有2种跳法。对于一个有n级台阶的楼梯来说，我们设跳法为 f(n) ，假如我们先跳1个台阶，则剩下有 n-1 个台阶，跳法为 f(n-1) 次，假如我们先跳2个台阶，则剩下 n-2 阶，跳法为 f(n-2)；由此可以推出，对于一个n阶的楼梯，有以下这个跳台阶的公式：
代码如下：
- #include <iostream>
- using namespace std;
- int JumpStep(int n)
- {
- if(n <= 0)
- return -1;
- if(n == 1)
- return 1;
- if(n == 2)
- return 2;
- return JumpStep(n-1)+JumpStep(n-2);
- }
- int main()
- {
- cout<<"5 step jumps : "<<JumpStep(5)<<endl;
- return 0;
- }
扩展：
当跳台阶的选择多了呢？比如说 每次可以跳3个台阶；按照同样的方法分析，如下公式：
解题代码如下：
- /**
- 题目描述：
- 有N个台阶，一个人从台阶下向上跳台阶，有两种跳的选择
- 1次跳一个台阶，1次跳两个台阶 这两种选择；
- */
- #include <iostream>
- using namespace std;
- int JumpStep(int n)
- {
- if(n <= 0)
- return -1;
- if(n == 1)
- return 1;
- if(n == 2)
- return 2;
- return JumpStep(n-1)+JumpStep(n-2);
- }
- int JumpStep3(int n)
- {
- if(n <= 0)
- return -1;
- if(n == 1)
- return 1;
- if(n == 2)
- return 2;
- if(n == 3)
- return 4;
- return JumpStep3(n-1)+JumpStep3(n-2)+JumpStep3(n-3);
- }
- int main()
- {
- cout<<"5 step jumps : "<<JumpStep(5)<<endl;
- cout<<"5 step jumps : "<<JumpStep3(5)<<endl;
- return 0;
- }
微信公众号： 猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。
