《編程之美》讀書筆記08：2.9 Fibonacci序列
計(jì)算Fibonacci序列最直接的方法就是利用遞推公式 F(n+2)=F(n+1)+F(n)。而用通項(xiàng)公式來(lái)求解是錯(cuò)誤的，用浮點(diǎn)數(shù)表示無(wú)理數(shù)本來(lái)就有誤差，經(jīng)過(guò)n次方后，當(dāng)n相當(dāng)大時(shí)，誤差能足夠大到影響浮點(diǎn)數(shù)轉(zhuǎn)為整數(shù)時(shí)的精度，得到的結(jié)果根本不準(zhǔn)。
用矩陣來(lái)計(jì)算，雖然時(shí)間復(fù)雜度降到O(log n)，但要用到矩陣類，相當(dāng)麻煩。觀察：
F(n+2)=F(n)+F(n-1)＝2*F(n-1)+F(n-2)=3*F(n-2)+2*F(n-4)
用歸納法很容易證明 F(n) = F(k)*F(n+1-k) + F(k-1)*F(n-k)，利用該遞推公式和原遞推公式，要計(jì)算F(n)，只要計(jì)算F([n/2])和F([n/2]+1)，時(shí)間復(fù)雜度為 O(lg n)。如：要計(jì)算F(58)，由 58 -> 29,30 -> 14,15 -> 7,8 -> 3,4 -> 1,2 可知只要算5次。可以用一個(gè)棧保存要計(jì)算的數(shù)，實(shí)際上，將n的最高位1（假設(shè)在第k位）左邊的0去除掉后，第m次要計(jì)算的數(shù)是第k位到第k-m+1位這m個(gè)位組成的值t(m)，則第m-1次要計(jì)算的數(shù)為t(m-1)，且
t(m)=2*t(m-1)+(第k-m+1位是否為1)。
若第m-1次計(jì)算得到了f(k)和f(k+1)，則第m次計(jì)算：
|
第k-m+1位
|
已計(jì)算
|
待計(jì)算
|
|
1
|
f(k)
f(k+1)
|
f(2*k+1),f(2*k+2)
|
|
0
|
f(2*k),f(2*k+1)
|
具體公式見下面代碼。
下面是計(jì)算F(n)最后四位數(shù)（某道ACM題）的代碼。
/* Fibonacci數(shù)列第N個(gè)數(shù)的最后4位數(shù)
注意，當(dāng) N>93 時(shí) 第N個(gè)數(shù)的值超過(guò)64位無(wú)符號(hào)整數(shù)可表示的范圍。
F(n+2)=F(n)+F(n-1) F(0)=0 F(1)=1 F(2)=1 ==>
F(n)=F(k)*F(n+1-k) + F(k-1)*F(n-k) ==>
F(2*n)=F(n+1)*F(n)+F(n)*F(n-1)=(F(n+1)+F(n-1))*F(n)=(F(n+1)*2-F(n))*F(n)
F(2*n+1)=F(n+1)*F(n+1)+F(n)*F(n)
F(2*n+2)=F(n+2)*F(n+1)+F(n+1)*F(n)=(F(n+2)+F(n))*F(n+1)=(F(n+1)+F(n)*2)*F(n+1)
*/
unsigned fib_last4( unsigned num)
{
if ( num == 0 ) return 0;
const unsigned M=10000;
unsigned ret=1,next=1,ret_=ret;
unsigned flag=1, tt=num;
while ( tt >>= 1) flag <<= 1;
while ( flag >>= 1 ){
if ( num & flag ){
ret_ = ret * ret + next * next;
next = (ret + ret + next) * next;
} else {
//多加一個(gè)M，避免 2*next-ret是負(fù)數(shù)，造成結(jié)果不對(duì)
ret_ = (next + next + M - ret) * ret;
next = ret * ret + next * next;
}
ret = ret_ % M;
next = next % M;
}
return ret;
}