转自：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;
- }
本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/archive/2012/12/13/2817101.html，如需转载请自行联系原作者
