苏木三少
错的不是你,而是这个世界。

递归-爬楼梯

爬楼梯

要点:用递归将问题分解为规模更小的子问题进行求解。

题目:

陶老师爬楼梯,他可以每次走1级或者2级,输入楼梯的级数,求不同的走法数。

eg:楼梯一共有3级,他可以每次都走一级,或者第一次走一级,第二次走两级,也可以第一次走两级,第二次走一级,一共三种方法。

输入:

 

输入包含若干行,每行包含一个正整数N,代表楼梯级数,1<=N<=30输出不同的走法数,每一行输入对应一行。

输出:

不同的走法数,每一行输入对应一行输出

 

样例输入:

5

8

10

 

样例输出:

8

34

89

解法:

n级台阶的走法 =先走一级后,n-1级台阶的走法+先走两级后,n-2级台阶的走法

f(n) = f(n-1)+f(n-2)

边界条件;说白了就是基线条件(递归的)

n < 0  0   n=0   1   n=1   1

n= 0   1   n= 1   1  n=2   2

C++源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# include<iostream>
using namespace std;
int N;
int stairs(int n){
    if( n< 0){
        return 0;
    }
    if(n == 0){
        return 1;
    }
    return stairs(n-1) + stairs(n-2);
}
int main(){
    while(cin>>N){
        cout<<stairs(N)<<endl;
    }
    return 0;
}

 

C++截图:

赞(3) 打赏
有问题的朋友随时留言,或者加我为好友。我的QQ是805375353. <<苏木三少博客 » 递归-爬楼梯

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

十年之约