【剑指offer】面试题九：斐波那契数列

题目：写一个函数，输入 n，求斐波那契（Fibonaci）数列的第 n 项。斐波那契数列的定义如下：

解法一、效率低下的递归解法

代码如下：

 1 // Fanbonacci.c
 2 #include "stdio.h"
 3 #include "stdlib.h"
 4 
 5 long long Fabonacci(unsigned int n)
 6 {
 7     if(n <= 0)
 8         return 0;
 9 
10     if(n == 1)
11         return 1;
12 
13     return Fabonacci(n-1) + Fabonacci(n-2);
14 }
15 
16 int main(int argc, char const *argv[])
17 {
18     int n = 10;
19 
20     long long sum = Fabonacci(n);
21     printf("Fabonacci: %lld
", sum);
22 
23     return 0;
24 }

View Code

该递归解法并不适合这道题目。因此这种解法存在很严重的效率问题。

我们以求解 f(10) 为例来分析递归的求解过程。想求 f(10)，需要先求得 f(9) 和 f(8)。同样的，想求得 f(9)，需要先求得 f(8) 和 f(7) ······ 我们可以中树形结构来表示这样依赖关系。如下图：

我们不难发现这棵树有很多结点是重复的，例如 f(8)、 f(7)、 f(6)、 f(5)··· 也就是说，树的右半部分都是重复计算的。试想一下当 n 是一个很大的数时，这样的重复计算量是很大的，因此递归解法会相当的慢。

解法二：

上述递归的方法之所以慢是因为重复的计算太多，那么有什么办法可以便面重复计算么？

最简单的办法就是从下往上计算，首先根据 f(0)和 f(1)算出 f(2)，再根据 f(1)和 f(2)算出 f(3)

······ 以此类推就可以算出第 n 项了，这样，这种算法的时间复杂度为 O(n)。

实现代码如下：

 1 // Fibonacci.c
 2 #include "stdio.h"
 3 #include "stdlib.h"
 4 
 5 long long Fibonacci(unsigned int n)
 6 {
 7     int result[2] = {0, 1};
 8     if(n < 2)
 9         return result[n];
10 
11     long long FibMinusTwo = result[0];
12     long long FibMinusOne = result[1];
13 
14     long long FibN = 0;
15     int i;
16     for(i = 2; i <= n; ++i)
17     {
18         FibN = FibMinusTwo + FibMinusOne;
19 
20         FibMinusTwo = FibMinusOne;
21         FibMinusOne = FibN;
22     }
23 
24     return FibN;
25 }
26 
27 int main(int argc, char const *argv[])
28 {
29     int n = 10;
30 
31     long long sum = Fibonacci(n);
32     printf("Fabonacci: %lld
", sum);
33 
34     return 0;
35 }

View Code

编译与执行：

1 gcc -o Fibonacci Fibonacci .c
2 ./Fibonacci

斐波那契数列的应用：

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

我们可以用 2 * 1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 8个 2*1的小矩形无重叠地覆盖一个 2*8 的大矩形，总共有多少种方法？

本文完。