Fibonacci數(shù)列
Fibonacci數(shù)列是一個(gè)非常美麗边臼、和諧的數(shù)列，有人說(shuō)它起源于一對(duì)繁殖力驚人崖堤、基因非常優(yōu)秀的兔子侍咱，也有人說(shuō)遠(yuǎn)古時(shí)期的鸚鵡就知道這個(gè)規(guī)律。
每一個(gè)學(xué)理工科的學(xué)生都知道Fibonacci數(shù)列密幔，F(xiàn)ibonacci數(shù)列由如下遞推關(guān)系式定義：
F(0)=0, F(1)=1, n>1時(shí)楔脯，F(xiàn)(n)=F(n-1)+F(n-2)。
每一個(gè)上過算法課的同學(xué)都能用遞歸的方法求解Fibonacci數(shù)列的第n+1項(xiàng)的值胯甩，即F(n),以下為相關(guān)算法的代碼:
int Fibonacci (int n)
{
if (n <= 0) return 0;
else if (n == 1) return 1;
else return Fibonacci(n-1) + Fibonacci(n-2);
}
那么問題來(lái)了,對(duì)于以上這種算法,能否進(jìn)一步優(yōu)化?
分析與解法
解法一:遞推關(guān)系式的優(yōu)化
上面列出的算法是根據(jù)遞推關(guān)系式的定義直接得出的,它在計(jì)算F(n)時(shí),需要計(jì)算從F(2)到F(n-1)每一項(xiàng)的值,這樣簡(jiǎn)單的遞歸式存在著很多的重復(fù)計(jì)算,如F(5) = F(4) + F(3) , 在求F(4)的時(shí)候也需要計(jì)算一次F(3)的大小...等等昧廷。請(qǐng)問這個(gè)算法的時(shí)間復(fù)雜度是多少?
那么經(jīng)過分析我們可以知道優(yōu)化此類算法的重點(diǎn)在于減少重復(fù)計(jì)算。那么我們可以用一個(gè)數(shù)組存儲(chǔ)所有已計(jì)算過的項(xiàng)偎箫。這樣就可以達(dá)到用空間換取時(shí)間的目的木柬。在這種情況下,時(shí)間復(fù)雜度為 O(N),而空間復(fù)雜度也為O(N)。
那么有更快的算法嗎?
解法二:求解通項(xiàng)公式
如果我們知道一個(gè)數(shù)列的通項(xiàng)公式,使用公式來(lái)計(jì)算就會(huì)更加容易了淹办。那么問題的關(guān)鍵就是能不能把這個(gè)函數(shù)的遞推公式計(jì)算出來(lái)眉枕。
由遞推公式: F(n)=F(n-1)+F(n-2),知道F(n)的特征方程為:
x2 = x + 1 , 有兩個(gè)特征根x1，x2。
則通項(xiàng)為F(n)= A x1 n + B x2 n( n次方,本人對(duì)markDown語(yǔ)法不是很熟練所以在此加以說(shuō)明希望不要誤導(dǎo)到讀者,以上公式為:A倍 x1 的n次方) 速挑，其中A谤牡，B可以通過F(0)和F(1)計(jì)算出來(lái)。
解法三:分治策略
因?yàn)镕ibonacci數(shù)列是二階遞推數(shù)列,所以存在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 }
拓展
假設(shè)A(0)=1，A(1)=2腊满，A(2)=2断序。對(duì)于n>2，都有A(k)=A(k-1)+A(k-2)+A(k-3)糜烹。```
(1) 對(duì)于任何一個(gè)給定的n，如何計(jì)算A(n)漱凝？
(2) 對(duì)于n非常大的情況疮蹦，如n=260的時(shí)候，如何計(jì)算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)這個(gè)問題筆者思路如下，但并未通過代碼證實(shí)：
A(n)modM取值為0壁公，1感论，2，...紊册，M-1比肄，為有限的，因此囊陡，三元組[A(k) A(k-1) A(k-2)]共有M3種可能芳绩。
因此，A(n)modM是周期數(shù)列撞反，而且妥色，周期最大為M3。
可以先求出周期T遏片，然后再求A[260]```
