雁过无痕

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::

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

 

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;
}


 



posted on 2010-06-23 23:28 flyinghearts 阅读(4680) 评论(11)  编辑 收藏 引用 所属分类: 算法编程之美

评论

# re: O(log n)求Fibonacci数列(非矩阵法)[未登录] 2010-07-16 11:18 Klion
你好,这篇文章下面这段文字“实际上,将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次计算:”
不是看的很懂,希望博主给解释下。
主要有以下几点疑问:1.那个最高位左边的是比最高位高的位还是低的位。
2.那个t(m)怎么算的  回复  更多评论
  

# re: O(log n)求Fibonacci数列(非矩阵法) 2010-07-18 05:16 dissertation service
A lot of years good people would like to order good enough history dissertation referring to this good post from the dissertation writing services. Can you in case suggest the experienced thesis writing services? Thanks a lot.   回复  更多评论
  

# re: O(log n)求Fibonacci数列(非矩阵法) 2010-07-21 00:35 flyinghearts
@Klion

以58为例其二进制表示(最左边的0省略)为:
  11 1010
t(1) 1
t(2) 11
t(3) 11 1
t(4) 11 10
t(5) 11 101
t(6) 11 1010

即:
t(1) = 1
t(2) = 3
t(3) = 7
t(4) = 14
t(5) = 29
t(6) = 58

  回复  更多评论
  

# re: O(log n)求Fibonacci数列(非矩阵法)[未登录] 2010-07-26 11:40 Klion
@flyinghearts
恩,谢谢了。后来我自己也动手划了下,原来我一开始没理解到,现在我知道那个t(m)怎么算的,也用自己的理解写了点求出这个是干嘛的。
我理解的就是这个t(m)其实就是一个逆向工程,先是判断右移(m-1)位之后的情况,看这个数是奇数还是偶数,如果是奇数就由哪两个数得来,如果是偶数,就由哪两个数得来,由这个可以得到我们要算的结果是算出来的这两个中的小者。  回复  更多评论
  

# re: O(log n)求Fibonacci数列(非矩阵法) 2010-08-02 23:34 flyinghearts
@Klion
58 -> 29 -> 14 -> 7 -> 3 -> 1
t(i)就是这个倒过来。
要计算 F(t(i)) 就要判断 t(i) 是 t(i-1)的2倍,还是2倍加1
(实际上,t(i)没必要计算,只要判断第k-m+1位是否为1就可以了。)
根据这两个情况,决定使用那几个公式。


我最初的代码,就是用一个栈,保存n每次右移1位的结果,
最后根据栈顶是否是奇数,来决定调用那两个公式,出栈。
反复至栈为空。



  回复  更多评论
  

# re: 《编程之美》读书笔记08:2.9 Fibonacci序列 —— O(log n)求Fibonacci数列(非矩阵法)[未登录] 2010-10-06 05:47 april
谢谢帖主的分享,不过code算出来的结果是错的,贴主有测试过吗?
递推公式 F(n+2)=F(n)+F(n-1) 是错的
正确的是 F(n+1)=F(n)+F(n-1), 我想这是为什么算出来的结果不是F(n), 而是F(n-1).
  回复  更多评论
  

# re: 《编程之美》读书笔记08:2.9 Fibonacci序列 —— O(log n)求Fibonacci数列(非矩阵法)[未登录] 2010-10-06 06:01 april
@april
收回我的评论,虽然递推公式写错(typo),但是code返回结果正确。。  回复  更多评论
  

# re: 《编程之美》读书笔记08:2.9 Fibonacci序列 —— O(log n)求Fibonacci数列(非矩阵法) 2010-12-02 23:34 flyinghearts
@april
确实把公式打错了:
F(n+2)=F(n)+F(n-1) 应该是 F(n+1) = F(n) + F(n-1)
不过后面的公式推导没问题。

  回复  更多评论
  

# re: 《编程之美》读书笔记08:2.9 Fibonacci序列 —— O(log n)求Fibonacci数列(非矩阵法) 2012-09-03 10:26
不过实测的结果:是matrix版(O(logn))最快,去递归的(bottom-up)版(O(n))次之,然后是这个版本(O(logn)),可能是乘法的缘故  回复  更多评论
  

# re: 《编程之美》读书笔记08:2.9 Fibonacci序列 —— O(log n)求Fibonacci数列(非矩阵法) 2013-04-26 23:21 card323
我写了一篇文章 ggboom.com/2013/04/26/ologn%E6%B1%82%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91fibonacci%E6%95%B0%E5%88%97/
欢迎拍砖  回复  更多评论
  

# re: 《编程之美》读书笔记08:2.9 Fibonacci序列 —— O(log n)求Fibonacci数列(非矩阵法) 2013-04-26 23:23 card323
@黄
试试我的算法:
ggboom.com/2013/04/26/ologn%E6%B1%82%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91fibonacci%E6%95%B0%E5%88%97/  回复  更多评论
  


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