《编程之美》读书笔记08：2.9 Fibonacci序列

《编程之美》读书笔记08：2.9 Fibonacci序列

计算Fibonacci序列最直接的方法就是利用递推公式 F(n+2)=F(n+1)+F(n)。而用通项公式来求解是错误的，用浮点数表示无理数本来就有误差，经过n次方后，当n相当大时，误差能足够大到影响浮点数转为整数时的精度，得到的结果根本不准。

用矩阵来计算，虽然时间复杂度降到O(log n)，但要用到矩阵类，相当麻烦。观察：

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)，利用该递推公式和原递推公式，要计算F(n)，只要计算F([n/2])和F([n/2]+1)，时间复杂度为 O(lg n)。如：要计算F(58)，由 58 -> 29,30 -> 14,15 -> 7,8 -> 3,4 -> 1,2 可知只要算5次。可以用一个栈保存要计算的数，实际上，将n的最高位1（假设在第k位）左边的0去除掉后，第m次要计算的数是第k位到第k-m+1位这m个位组成的值t(m)，则第m-1次要计算的数为t(m-1)，且

t(m)=2*t(m-1)+(第k-m+1位是否为1)。

若第m-1次计算得到了f(k)和f(k+1)，则第m次计算：

具体公式见下面代码。

下面是计算F(n)最后四位数（某道ACM题）的代码。

/*Fibonacci数列第N个数的最后4位数

注意，当N>93时第N个数的值超过64位无符号整数可表示的范围。

F(n+2)=F(n)+F(n-1)F(0)=0F(1)=1F(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)

*/

unsignedfib_last4(unsignednum)

{

if(num==0)return0;

constunsignedM=10000;

unsignedret=1,next=1,ret_=ret;

unsignedflag=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{

//多加一个M，避免2*next-ret是负数，造成结果不对

ret_=(next+next+M-ret)*ret;

next=ret*ret+next*next;

}

ret=ret_%M;

next=next%M;

}

returnret;

}