• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            雁過無痕

              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 閱讀(4723) 評論(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/  回復  更多評論
              

            久久精品国产2020| 国产69精品久久久久9999| 人人妻久久人人澡人人爽人人精品| 久久久久国产视频电影| 亚洲国产精品无码久久青草| 精品熟女少妇AV免费久久| 国产精品久久久久久久久鸭| 久久最新免费视频| 久久国产精品成人影院| 少妇久久久久久被弄到高潮| 老色鬼久久亚洲AV综合| 伊人久久无码精品中文字幕| www性久久久com| 国产偷久久久精品专区| 精品国产乱码久久久久久浪潮| 人妻无码中文久久久久专区| 久久精品不卡| 久久精品国产影库免费看| 热99RE久久精品这里都是精品免费| 国产精品永久久久久久久久久| 久久亚洲精品人成综合网| 狠狠色丁香婷婷久久综合 | 久久久久久曰本AV免费免费| 亚洲狠狠久久综合一区77777| 无码人妻久久久一区二区三区| 久久久久97国产精华液好用吗| 国产成人AV综合久久| 无码人妻久久一区二区三区免费| 狠狠色丁香久久婷婷综合图片 | 久久精品国产69国产精品亚洲| 无码国内精品久久人妻| 天天躁日日躁狠狠久久| 久久婷婷国产剧情内射白浆 | 久久精品无码一区二区无码| 99蜜桃臀久久久欧美精品网站| 中文字幕久久亚洲一区| 久久中文字幕人妻熟av女| 性做久久久久久久久浪潮| 2021久久精品免费观看| 欧美精品国产综合久久| 久久国产精品77777|