• <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>

            5D空間

            學習總結與經驗交流

               :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
              遞歸數列a(n) = r1*a(n-1) + r2*a(n-2)
              其中r1 r2是常數,a1 a2已知,按照順序a1 a2 r1 r2 n輸入參數,則返回這樣一個遞歸數列的第n項值。類型均為double

            #ifndef FINDAN_H
            #define FINDAN_H

            #include 
            <cmath>

            // a(n) = r1*a(n-1) + r2*a(n-2), give the a1, a2, r1, r2 and n
            double findAnWithDegreeOfTwo( double a1, double a2, double r1, double r2, int n )
            {
                
            double x1;
                
            double x2;
                
            double u1;
                
            double u2;
                
            double det = r1*r1 + 4*r2;
                
            double result;

                
            if ( det < 0 )
                    
            return 0;
                
            else if ( det > 0 )
                
            {
                    det 
            = sqrt( det );
                    x1 
            = ( r1 + det ) / 2;
                    x2 
            = ( r1 - det ) / 2;
                    u1 
            = ( a1*x2 - a2 ) / ( x1*( x2 - x1 ) );
                    u2 
            = ( a2*x1 - a1 ) / ( x2*( x1 - x2 ) );
                    result 
            = u1*pow( x1, n ) + u2*pow( x2, n );
                    
            return result;
                }

                
            else
                
            {
                    x1 
            = r1 / 2;
                    u2 
            = ( a2 - x1*a1 ) / x1*x1;
                    u1 
            = a1 / x1 - u2;
                    result 
            = ( u1 + u2*n ) * pow( x1, n );
                    
            return result;
                }

            }


            #endif
            posted on 2011-04-03 19:53 今晚打老虎 閱讀(1034) 評論(4)  編輯 收藏 引用 所屬分類: 我的開源庫

            評論

            # re: findAnWithDegreeOfTwo(計算度數為2的齊次遞歸數列的第n項) 2011-04-05 15:24 Singa
            這樣做的時間復雜度是O(n),可以利用矩陣乘法來做,把時間復雜度降低到O(logn)。  回復  更多評論
              

            # re: findAnWithDegreeOfTwo(計算度數為2的齊次遞歸數列的第n項) 2011-04-08 10:00 今晚打老虎
            @Singa
            矩陣乘法么,沒學過耶,能指點一下么  回復  更多評論
              

            # re: findAnWithDegreeOfTwo(計算度數為2的齊次遞歸數列的第n項) 2011-04-11 17:47 Singa
            @今晚打老虎
            就這個問題的話
            a[n] a[n-1] r1 1 a[n+1] a[n]
            a[n-1] a[n-2] r2 0 a[n] a[n-1]
            上面分別是三個2*2的矩陣,前兩個相乘得到第三個
            這樣子就得到一個類似等比數列的遞推式了
            r1 1
            r2 0 類似于公比

            a[2] a[1]
            a[1] a[0] 類似于數列首項
            然后算公比的n次方的時候用下快速冪取模,就實現O(logn)的復雜度了  回復  更多評論
              

            # re: findAnWithDegreeOfTwo(計算度數為2的齊次遞歸數列的第n項) 2011-04-12 00:24 今晚打老虎
            @Singa
            感謝指點!  回復  更多評論
              

            国产成人精品久久免费动漫 | 久久青青草原精品影院| 久久婷婷五月综合色奶水99啪 | 亚洲精品无码久久久久久| 久久久久无码精品国产| 国产成人久久精品二区三区| 亚洲婷婷国产精品电影人久久| 97久久婷婷五月综合色d啪蜜芽| 国产精品女同久久久久电影院| 国产精品综合久久第一页| 99久久无色码中文字幕人妻| 亚洲伊人久久大香线蕉苏妲己| 伊人色综合久久天天网| 亚洲伊人久久大香线蕉苏妲己| 亚洲中文字幕无码一久久区| 精品国产综合区久久久久久| 久久国产乱子伦免费精品| 久久伊人中文无码| 久久久精品一区二区三区| 综合久久国产九一剧情麻豆| 久久五月精品中文字幕| 久久91精品久久91综合| 久久夜色精品国产噜噜麻豆| 久久久久亚洲AV无码专区桃色 | 亚洲国产高清精品线久久 | 久久久久国产视频电影| 久久r热这里有精品视频| 久久国产免费直播| 要久久爱在线免费观看| 久久无码国产| 亚洲精品tv久久久久久久久久| 久久国产综合精品五月天| 色噜噜狠狠先锋影音久久| 狠狠色丁香久久婷婷综合五月| 人妻精品久久久久中文字幕69| 亚洲av日韩精品久久久久久a| 精品国产乱码久久久久软件| 久久亚洲熟女cc98cm| 免费精品久久天干天干| 亚洲人成精品久久久久| 无码日韩人妻精品久久蜜桃 |