久久五月婷婷丁香社区,欧美国产综合视频,欧美日本三区

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

　　遞歸數(shù)列a(n) = r1*a(n-1) + r2*a(n-2)
　　其中r1 r2是常數(shù)，a1 a2已知，按照順序a1 a2 r1 r2 n輸入?yún)?shù)，則返回這樣一個遞歸數(shù)列的第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 今晚打老虎閱讀(1049) 評論(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的矩陣，前兩個相乘得到第三個
這樣子就得到一個類似等比數(shù)列的遞推式了
r1 1
r2 0 類似于公比

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

# re: findAnWithDegreeOfTwo(計算度數(shù)為2的齊次遞歸數(shù)列的第n項) 2011-04-12 00:24 今晚打老虎

@Singa
感謝指點！回復更多評論

刷新評論列表

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

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

網(wǎng)站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

5D空間

留言簿

隨筆分類(18)

文章分類

搜索

積分與排名

最新隨筆

最新評論

閱讀排行榜

評論