当前位置:首页 » 面试笔试 » 正文

程序员面试题-跳台阶问题

11651 人参与  2019年03月14日 10:18  分类 : 面试笔试  评论

题目描述:

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

题目解析:

比如只有一个台阶,这个时候这只青蛙没有第二种选择,只能一次跳1级台阶,也就是只有一种跳法。

比如共有2个台阶呢?此时,这只青蛙就有两种选择了,第一种选择是一次跳1级,跳两次。第二种选择是一次跳2级,跳一次。

.......

那么共有n级台阶呢,通过大脑想这个过程实在是过于复杂,尤其n特别大时,已经超过了人脑的计算范围,那么我们就只好借助计算机的超高能力的计算来得到结果了,我们分析一下。

倒过来思考一下,比如这只青蛙已经跳到了第n级台阶,此时它正站在第n级台阶上沾沾自喜呢,那么,它的上一步是什么呢?因为青蛙一次只能跳1或2级台阶,所以,上一步这只青蛙一定在第n-1或者n-2级台阶上。

因此我们得到:

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

这个公式大家应该不会陌生吧,显然,有了这个公式,就很容易实现递归算法了。

递归算法实现需要两个条件,第一是初始条件,第二就是递归公式了。下面我们来看看初始条件。

f(n)=f(n-1)+f(n-2)这个公式里,当n大于等于3时,f(n-1)和f(n-2)里的n-1大于等于2,n-2大于等于1。所以这个公式适用于n大于等于3的情况。f(1)是指共1级台阶几种走法,显然等于1,就是一种走法。f(2)=2,前面讨论过了。代码如下:

int jumpFloor(int number) {
        if(number==1)
            return 1;
        else if(number==2)
            return 2;
        else
        {
            return(jumpFloor(number-1)+jumpFloor(number-2));
        }
    }

是不是很简单啊!

确实,递归算法确实简单,容易理解,但是它的时间复杂度比较大,这个递归里有很多重复的计算,还有不断进栈退栈的过程。想一想能不能不用递归直来直去的得到答案呢?

当然可以!

还是借助f(n)=f(n-1)+f(n-2)这个公式:

台阶总数:1  2   3  4  5  6

走法共计:1  2   3  5  8  13

类似于赔多纳妾数列,代码如下:

  int jumpFloor(int number) {
        int i,l,r,sum=0;
        l=1,r=2;
        if(number==1)return 1;
        else if(number==2)return 2;
        for(i=0;i<number-2;i++)
        {
            sum=l+r;
            l=r;
            r=sum;
        }
        return sum;
    }


来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=1229

程序员面试  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!