NC68 跳台阶

63 阅读 0 评论 42 点赞

我是靠谱客的博主魁梧镜子，最近开发中收集的这篇文章主要介绍NC68 跳台阶，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

示例：

输入：2 返回值：2

说明：青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2

思路：

这一类题一般都能找到规律，然后通过规律来进行解答。这道题可以用两种方法来解决，一是解斐波那契的方法，二是递归。

1、斐波那契数列解法：

如上图，从最上面开始找规律，就能发现每次跳的次数能构成斐波那契数列（0，1，2，3，5，8)，所以可以用斐波那契的解法来算出跳n阶台阶能有集中方式。

代码及详情如下：

int jumpFloor(int number ) {//number为给定的台阶数
//当number是0，1，2中的一个时，是可以直接确定出来结果的
    if(number==0)
        return 0;
    if(number==1)
        return 1;
    if(number==2)
        return 2;
//定义斐波那契数列的前两个数
    int i=1;
    int j=2;
//定义第三个数，同时也是最终的的方法个数
    int k;
    for(int m=2;m<number;m++){
        k=i+j;
        i=j;
        j=k;
    }
    return k;
}

2、递归算法

思路：

很典型的采用分治法的思想来解决的问题

首先当问题规模很小时，即number=1和2时，分别对应1和2种跳台阶的方法；

当number>2时则要考虑跳第一个台阶的时候，如果是一次跳1则还要考虑number-1的跳法有多少种，如果一次跳2则还要考虑number-2的跳法有多少种；

就比如现在有五个台阶：

1、第一次用一次一阶的跳法跳了，那么还剩下四阶，就还需考虑这四阶的总的跳法；

1.1、这第四阶的第一次用一次一阶的跳法跳了，那么还剩下三阶，就还需考虑这三阶的总跳法；

……

1.2、这第四阶的第一次用一次两阶的跳法跳了，那么还剩下两阶，就还需考虑这两阶的总跳法。

……

2、第一次用一次两阶的跳法跳了，那么还剩下三阶，就还需考虑这一阶的总的跳法。

……

所以总的跳法应该是这两种可能的跳法都加起来。

代码及详情如下：

int jumpFloor(int number ) {
//这三种情况是可以直接得到的
    if(number==0)
        return 0;
    if(number==1)
        return 1;
    if(number==2)
        return 2;
//采用递归，将两种跳法的所有可能情况都加起来
    int n=jumpFloor(number-1)+jumpFloor(number-2);
    return n;
}