此處的C++斐波那契數列是如何實現的?

01-21

這裡的x,y,a,b,t分別代表什麼？是如何implement的？不理解啊嗚~(&>_

這是Fibonacci的二分演算法,時間複雜度為 $O(logn)$

鑒於初學者,我盡量詳細解答(這個代碼寫得也是夠晦澀難懂的,一定是喪心病狂的ACM選手寫出來的):

Fibonacci數列中有恆等式:

$F_{2n+1}=F_{n+1}^2+F_{n}^2$ (式1)

$F_{2n}=2F_{n}F_{n+1}-F_{n}^2$ (式2)

$F_{m+n}=F_{n+1}F_{m}+F_{n}F_{m-1}$ (式3)

(式1)和(式2)可由(式3)帶入m=n推得.

一個數的二進位表示為:

$n=n_1*2^0+n_2*2^1+n_3*2^2+...+n_i*2^{i-1}$

$n_i$ 為n的二進位數的數碼為0或1.

好來看代碼,我來一行行解釋這是怎麼回事:

double Fibonacci(int n){ double x = 1.0, y = 1.0, a = 0, b = 1.0,t; while (n&>0) { if (n 1){ t = a*x + b*y; a = x*(b - a) + a*y; b = t; } t = 2 * x*y - x*x; y = x*x + y*y; x = t; n &>&>= 1; } return a; }

先看循環體:

while (n&>0) { if (n 1){ //... } //... n &>&>= 1; }

這個循環表示遍歷n的每一位,其中if若表示n的最後一位是否為1.最後的n &>&>= 1;表示每次將n所有位右移一位,則相當於循環中遍歷n的每一個數位.

第一行:

double x = 1.0, y = 1.0, a = 0, b = 1.0,t;

初始化,幾個變數分別儲存的值為:

x: $F_{2^{i}}$

y: $F_{2^{i}+1}$

a: $F_{alpha }$

b: $F_{alpha +1}$

t: 迭代中的臨時變數

其中i表示循環過程中當前對應n的第i位, $alpha$ 為n的前i位表示的數值 $alpha =n_1*2^0+n_2*2^1+n_3*2^2+...+n_{i-1}*2^{i-2}$

初始時:x= $F_1$ =1; y= $F_2$ =1; $alpha$ =0; a= $F_0$ =0; b= $F_1$ =1;

當循環結束後有n=0, $alpha =n$

則a= $F_{n }$ ,為Fibonacci數列第n項,返回a

return a;

然後看循環體中最關鍵的部分:

先看這裡,a: $F_{alpha }$ 和b: $F_{alpha +1}$ 的部分:

if (n 1){ t = a*x + b*y; a = x*(b - a) + a*y; b = t; }

如果n的第i位 $n_i$ 為1則:

由: $F_{m+n}=F_{n+1}F_{m}+F_{n}F_{m-1}$ 得到:

$F_{alpha ^{$

對應:

t = a*x + b*y; //... b = t;

$F_{alpha ^{$

對應:

a = x*(b - a) + a*y;

然後是這裡:

t = 2 * x*y - x*x; y = x*x + y*y; x = t;

由

$F_{2n}=2F_{n}F_{n+1}-F_{n}^2$

$F_{2n+1}=F_{n+1}^2+F_{n}^2$

代入 $F_{2^{i}}$ 和 $F_{2^{i}+1}$ 計算得出: $F_{2^{i+1}}$ 和 $F_{2^{i+1}+1}$ 即是x,y

喵了個咪的,一開始看到和 @Milo Yip 一樣也以為是矩陣乘法展開,時間複雜度也為 $O(logn)$ ,答完了發現不是,算了還是不刪了,還是留著順便給題主參考一下:

Fibonacci的遞推式為:

$F_n=F_{n-1}+F_{n-2}$

用矩陣的方式表示可得:

$egin{bmatrix} F_n F_{n-1} \ 0 0 end{bmatrix} = egin{bmatrix} F_{n-1}+F_{n-2}F_{n-1} \ 0 0 end{bmatrix}=egin{bmatrix} F_{n-1} F_{n-2} \ 0 0 end{bmatrix}egin{bmatrix} 1 1 \ 1 0 end{bmatrix}$

即: $M_n=M_{n-1}C$

$left( M_n=egin{bmatrix} F_n F_{n-1} \ 0 0 end{bmatrix} , C=egin{bmatrix} 1 1 \ 1 0 end{bmatrix} ight)$

矩陣乘滿足結合律,可得通項公式為:

$M_n=M_2C^{n-2} quad (ngeq 2)$

$left( M_2=egin{bmatrix} 1 1 \ 0 0 end{bmatrix} ight)$

最後使用二分法計算 $C^{n-2}$ :

n為偶數: $C^n=left(C^{frac{n}{2} } ight) ^2$ n為奇數: $C^n=left(C^{frac{n-1}{2} } ight) ^2C$

結果為 $F_n=M_{n_{1,1}}$

如果還有什麼地方講得不清楚可以手動模擬一下也歡迎來問~

最後吐槽一下用double...

這種矩陣技巧複雜度是logn，他主要是為了解決你用通項公式時出現黃金分割數求冪精度丟失。通項可由矩陣對角化得出。所以通過矩陣有時可以容易保存精度。具體在mit的演算法導論公開課分治法也有說到。公開課視頻地址

http://v.163.com/movie/2010/12/8/U/M6UTT5U0I_M6V2T998U.html？

逆向工程好難，推了好久，終於看懂了。。。

可以認為它在用二分的方法來求Fibnacci數。

這裡的Fibnacci數的定義為F[0] = 0, F[1] = 1, F[2] = 1, F[3] = 2, ...

由Fibnacci數的性質 $F_{m+n+1} = F_{m+1} F_{n+1} + F_{m} F_{n}$

設 $v_i = egin{bmatrix} F_i \ F_{i+1} end{bmatrix}$ ，則

$v_{m+n} = egin{bmatrix} F_{m+m} \ F_{m+n+1} end{bmatrix} = egin{bmatrix} F_{m+1} F_{n} + F_{m} F_{n-1} \ F_{m+1} F_{n+1} + F_{m} F_{n} end{bmatrix} = egin{bmatrix} F_{m+1} F_{n} + F_{m} ( F_{n+1} - F_{n} ) \ F_{m+1} F_{n+1} + F_{m} F_{n} end{bmatrix}$