题目：写一个函数，输入 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\n", sum);22 23     return 0;24 }

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

我们以求解 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\n", sum);33 34     return 0;35 }

 

编译与执行：

1 gcc -o Fibonacci Fibonacci .c2 ./Fibonacci

 

斐波那契数列的应用：

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

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

 

本文完。