Fibonacci数列
Fibonacci数列是一个非常美丽、和谐的数列，有人说它起源于一对繁殖力惊人、基因非常优秀的兔子，也有人说远古时期的鹦鹉就知道这个规律。
每一个学理工科的学生都知道Fibonacci数列，Fibonacci数列由如下递推关系式定义：
F(0)=0, F(1)=1, n>1时，F(n)=F(n-1)+F(n-2)。
每一个上过算法课的同学都能用递归的方法求解Fibonacci数列的第n+1项的值，即F(n),以下为相关算法的代码:
int Fibonacci (int n)
{
if (n <= 0) return 0;
else if (n == 1) return 1;
else return Fibonacci(n-1) + Fibonacci(n-2);
}
那么问题来了,对于以上这种算法,能否进一步优化?
分析与解法
解法一:递推关系式的优化
上面列出的算法是根据递推关系式的定义直接得出的,它在计算F(n)时,需要计算从F(2)到F(n-1)每一项的值,这样简单的递归式存在着很多的重复计算,如F(5) = F(4) + F(3) , 在求F(4)的时候也需要计算一次F(3)的大小...等等。请问这个算法的时间复杂度是多少?
那么经过分析我们可以知道优化此类算法的重点在于减少重复计算。那么我们可以用一个数组存储所有已计算过的项。这样就可以达到用空间换取时间的目的。在这种情况下,时间复杂度为 O(N),而空间复杂度也为O(N)。
那么有更快的算法吗?
解法二:求解通项公式
如果我们知道一个数列的通项公式,使用公式来计算就会更加容易了。那么问题的关键就是能不能把这个函数的递推公式计算出来。
由递推公式: F(n)=F(n-1)+F(n-2),知道F(n)的特征方程为:
x² = x + 1 , 有两个特征根x1，x2。
则通项为F(n)= A x1 n + B x2 n( n次方,本人对markDown语法不是很熟练所以在此加以说明希望不要误导到读者,以上公式为:A倍 x1 的n次方) ，其中A，B可以通过F(0)和F(1)计算出来。
解法三:分治策略
因为Fibonacci数列是二阶递推数列,所以存在2*2的矩阵A，使得：
[Fn Fn-1] = [Fn-1, Fn-2]*A
通过递推可以求得A={{1, 1}{1, 0}}
且：[Fn Fn-1] = [Fn-1, Fn-2]*A = [Fn-2, Fn-3]*A2= ... = [F1, F0]*An-1
剩下的问题就是求解矩阵A的方幂。
参考代码如下：
1 #include <iostream>
2 using namespace std;
3
4 typedef long long LL;
5 const int maxn = 2;
6 const int MOD = 100000007;
7
8 struct Matrix
9 {
10 LL m[maxn][maxn];
11 };
12
13 Matrix A = {1, 1, 1, 0};
14 Matrix I = {1, 0, 0, 1};
15
16 Matrix multi(Matrix a, Matrix b)
17 {
18 Matrix c;
19 for (int i = 0; i < maxn; i++)
20 {
21 for (int j = 0; j < maxn; j++)
22 {
23 c.m[i][j] = 0;
24 for (int k = 0; k < maxn; k++)
25 {
26 c.m[i][j] += a.m[i][k] * b.m[k][j] % MOD;
27 }
28 c.m[i][j] %= MOD;
29 }
30 }
31 return c;
32 }
33
34 Matrix power(Matrix A, int k)
35 {
36 Matrix ans = I, p = A;
37 while (k)
38 {
39 if (k & 1)
40 {
41 ans = multi(ans, p);
42 k--;
43 }
44 k >>= 1;
45 p = multi(p, p);
46 }
47 return ans;
48 }
49
50 int main(int argc, char *argv[])
51 {
52 int n;
53 while (cin >> n)
54 {
55 if (n <= 0)
56 {
57 cout << 0 << endl;
58 continue;
59 }
60 Matrix ans = power(A, n-1);
61 cout << ans.m[0][0] << endl;
62 }
63 }
拓展
假设A(0)=1，A(1)=2，A(2)=2。对于n>2，都有A(k)=A(k-1)+A(k-2)+A(k-3)。```
(1) 对于任何一个给定的n，如何计算A(n)？
(2) 对于n非常大的情况，如n=260的时候，如何计算A(n)modM(M<100000)呢？```
解答：
(1) [A(k) A(k-1) A(k-2)] = [A(k-1) A(k-2) A(k-3)]*B
其中B={{1, 1, 0}, {1, 0, 1}, {1, 0, 0}}。
(2)这个问题笔者思路如下，但并未通过代码证实：
A(n)modM取值为0，1，2，...，M-1，为有限的，因此，三元组[A(k) A(k-1) A(k-2)]共有M3种可能。
因此，A(n)modM是周期数列，而且，周期最大为M3。
可以先求出周期T，然后再求A[260]```
