5D空間

學習總結與經驗交流

:: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

findAnWithDegreeOfTwo(計算度數為2的齊次遞歸數列的第n項)

　　遞歸數列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 今晚打老虎閱讀(1026) 評論(4) 編輯收藏引用所屬分類: 我的開源庫

@今晚打老虎
就這個問題的話
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
感謝指點！回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: PointerPool(指針池) LHRODT(非遞歸求解度數為2的線性齊次方程的第n項） probability(概率發生器) findAnWithDegreeOfTwo(計算度數為2的齊次遞歸數列的第n項) Zeller(計算某一天是星期幾）

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

5D空間

留言簿

隨筆分類(18)

文章分類

搜索

積分與排名

最新隨筆

最新評論

閱讀排行榜

評論