The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

O(log n)求Fibonacci数列(非矩阵法)

《编程之美》读书笔记: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次计算:

 

k-m+1

已计算

待计算

1

f(k)

f(k+1)

f(2*k+1),f(2*k+2)

0

f(2*k),f(2*k+1)

 

具体公式见下面代码。

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


 

/*   Fibonacci数列第N个数的最后4位数
    注意,当 N>93 时 第N个数的值超过64位无符号整数可表示的范围。
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 {
      
//多加一个M,避免 2*next-ret是负数,造成结果不对
      ret_ = (next + next + M - ret) * ret;
      next 
= ret * ret + next * next;
    }
    ret 
= ret_ % M;
    next 
= next % M;
  }
  
return ret;
}
转自:http://www.cppblog.com/flyinghearts/archive/2010/06/23/118593.html

posted on 2010-06-26 12:48 abilitytao 阅读(565) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理