剑指offer：跳台阶（循环和递归）

180 阅读 0 评论 119 点赞

我是靠谱客的博主小巧信封，这篇文章主要介绍剑指offer：跳台阶（循环和递归），现在分享给大家，希望可以做个参考。

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析：

考虑1个台阶，只有1跳法，则 f(1) = 1

考虑2个台阶，可以1级级条，可以一次跳2级，有两种跳法,则f(2) = 2

考虑3个台阶，它可以由1级跳来得到，也可以由2级跳来得到，所以它的跳法为 f(3-1) + f(3-2) = f(1) + f(2)

考虑n个台阶，它的跳法为 f(n-1) + f(n-2)

实则上为斐波那契数列。可以用递归，也可以用循环方法求解。

代码：

int jumpFloor(int number) {
	int fn;
        int f1 = 1, f2 = 2;
        if(number<0) return 0;
        if(number == 1) return f1;
        if(number == 2) return f2;
        int count = 3;
        fn = f1 + f2;
        while(count<number){
            f1 = f2;
            f2 = fn;
            fn = f1 + f2;
            count++;
        }
        
        return fn;
        
}