题目一 求斐波那契数列的第n项
写一个函数，输入n，求斐波那契(Fibonacci)数列的第n项。斐波那契数列的定义如下：
分析
递归法
给出的公式用递归是最简单的，但是也是效率很低的。
C
#include<stdio.h> long long Fibonacci(int n) { if (n <= 0) { return 0; } if (n == 1) { return 1; } return Fibonacci(n - 1) + Fibonacci(n - 2); } int main() { long long int value = Fibonacci(10); printf("value:%lld\n", value); return 0; }
我们来讨论为什么说递归实现斐波那契数列效率低。看下图
仅仅列举了几行就可以看到同一个数字被重复计算多次，用递归方法计算时间复杂度是以n的指数增长。所以我们一般不推荐用这种方法。
下图是n=30的执行时间为3s，可想而知速度多慢
记忆化递归法
上面的递归效率低的问题关键所在是计算重复的。所以我们可以用一个n大小的数组来存储之前的结果。时间复杂度O(n),空间复杂度O(n)。
测试数据n=100，是秒出结果（这里不考虑溢出问题）
C
#include<stdio.h> #include<stdlib.h> long long Fibonacci(int n) { if (n < 2) { return n; } long long * a = (long long*)malloc(sizeof(long long) * n); if (NULL == a) { perror("申请空间失败！"); } for (int i = 2; i <= n; i++) { a[i] = a[i - 1] + a[i - 2]; } return a[n - 1]; } int main() { long long int value = Fibonacci(100); printf("value:%lld\n", value); return 0; }
动态规律
分析上面那种方法，我们可以看到构造出来的数组实际有用的只是最近的俩个值，其他的值都可以不用，那么我们可以设计一个动态的，以斐波那契数列性质 f(n + 1) = f(n) + f(n - 1)为转移方程。
时间复杂度O(n),空间复杂度O(1)。
C
long long Fibonacci(int n) { long long first = 0; long long second = 1; long long sum = 0; if (n < 2) { return n; } for (int i = 2; i <= n; i++) { sum = first + second; first = second; second = sum; } return sum; } int main() { long long int value = Fibonacci(10); printf("value:%lld\n", value); return 0; }
题目二 青蛙跳台阶问题
一只青蛙一次可以跳上一级台阶，也可以跳上俩级台阶。求该青蛙跳完上一个n级的台阶总共有多少种跳法。
分析
我们可以找到一个规律：
上一个n级的台阶总数=上一个n-1级台阶总数+上一个n-2级台阶总数
有0个台阶时候：1种方法
有一个台阶时候：1种方法
有二个台阶时候：2种方法
有三个台阶时候：3种方法
1 1 2 3 5 8 13 … 实际就是斐波那契数列，解法和上面如出一辙，不再赘述。
相关题目
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形，请问用8个21的小矩形无重叠的覆盖一个2*8的大矩形时。总共有多少种方法？
分析
我们将2*8的覆盖方法设为f(8)。假设小矩形竖着放，剩下的即为f(7)。小矩形横着放在左下角那么上面也必须横着放，剩下的即为f(6)；因此f(8)=f(7)+f(6); 本质还是斐波那契数列。解法和上面如出一辙，不再赘述。
本章完
