斐波那契数列

发表于

面试题10：题目一：求斐波那契数列的第n项。

写一个函数，输入n，求斐波那契数列（Fibonacci）数列的第n项。
斐波那契数列f(n),
f(0) = 0,
f(1) = 1,
n > 1时f(n) = f(n-1)+f(n-2)。

OC形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
- (NSInteger)fibonacciWithNum:(NSUInteger)n {
    int result[2] = {0, 1};
    if (n < 2) {
        return result[n];
    }
    
    NSInteger fibNMinusOne = 1;
    NSInteger fibNMinusTwo = 0;
    NSInteger fibN = 0;
    for (NSUInteger i = 2; i <= n; ++i) {
        fibN = fibNMinusOne + fibNMinusTwo;
        fibNMinusTwo = fibNMinusOne;
        fibNMinusOne = fibN;
    }
    
    return fibN;
}

思路

用递归方法计算的时间复杂度是以n的指数的方式递增的。对递归方法进行改进，思路是避免重复计算。
把递归的算法用循环实现，从下往上计算。

时间复杂度

时间复杂度为O(n)。

拓展

面试题10：题目二：青蛙跳台阶问题。

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

思路

如果只有1级台阶，那显然只有一种跳法，如果有二级台阶，那就有两种跳法。
把n级台阶看成是n的函数记为f(n)。当n>2时，第一次跳的时候就有两种不同的选择：
一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)；二是第一次跳两级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此，n级台阶的不同跳法总数f(n)=f(n-1)+f(n-2)。实际上还是斐波那契数列。