跳台阶问题-白红宇

转自：

题目：

给定一个有N个台阶的楼梯，一个人从下到上开始跳台阶，这个人有两种跳的方式：一次跳一个台阶，一次跳两个台阶；

问：从台阶底端跳到台阶顶端，有多少种跳台阶的方式？

分析：

首先我们考虑最简单的情况。如果只有1个台阶，那么显然只有一种跳法；如果是2级台阶，那么有2种跳法。对于一个有n级台阶的楼梯来说，我们设跳法为 f(n) ，假如我们先跳1个台阶，则剩下有 n-1 个台阶，跳法为 f(n-1) 次，假如我们先跳2个台阶，则剩下 n-2 阶，跳法为 f(n-2)；由此可以推出，对于一个n阶的楼梯，有以下这个跳台阶的公式：

代码如下：

[cpp]
#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个台阶；按照同样的方法分析，如下公式：

解题代码如下：

[cpp]

题目描述：

有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，如需转载请自行联系原作者