Fibonacci数列

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]```