C++ 楼梯的走法

楼梯的走法 (100/100 分数)

题目描述

假设有n阶楼梯，小明一次可以选择走1阶，也可以选择走2阶，问多少种走法。比如有5阶台阶，共有8种走法。

1 1 1 1 1
1 1 1 2
1 1 2 1
1 2 1 1
1 2 2
2 1 1 1
2 1 2
2 2 1

要求使用递归解法。

输入描述

输入n，表示n阶楼梯，1<=n<=40

输出描述

输出楼梯的走法总数。

样例输入

5

样例输出

8

注释：本质上是斐波那契数列

#include <iostream>
using namespace std;

int step(int n){
    if(n<=0){
        return 0;
    }else if (n==1)
    {
        return 1;
    }else if (n==2){
        return 2;
    }
    return step(n-1)+step(n-2);
}

int main(){
    int n;
    cin >> n;
    cout << step(n);
    return 0;
}

这个问题本质上是斐波那契数列，假设只有一个台阶，那么只有一种跳法，那就是一次跳一级，f(1)=1；如果有两个台阶，那么有两种跳法，第一种跳法是一次跳一级，第二种跳法是一次跳两级,f(2)=2。如果有大于2级的n级台阶，那么假如第一次跳一级台阶，剩下还有n-1级台阶，有f(n-1)种跳法，假如第一次条2级台阶，剩下n-2级台阶，有f(n-2)种跳法。这就表示f(n)=f(n-1)+f(n-2)。将上面的斐波那契数列代码稍微改一下就是本题的答案。我们来看一下代码的实现。

————————————————

原文链接：https://blog.csdn.net/u010983881/java/article/details/50462951