5D空間

學(xué)習(xí)總結(jié)與經(jīng)驗(yàn)交流

:: 管理 ::

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

　　遞歸數(shù)列a(n) = r1*a(n-1) + r2*a(n-2)
　　其中r1 r2是常數(shù)，a1 a2已知，按照順序a1 a2 r1 r2 n輸入?yún)?shù)，則返回這樣一個(gè)遞歸數(shù)列的第n項(xiàng)值。類型均為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) 評(píng)論(4) 編輯收藏引用所屬分類: 我的開源庫(kù)

評(píng)論

# re: findAnWithDegreeOfTwo(計(jì)算度數(shù)為2的齊次遞歸數(shù)列的第n項(xiàng)) 2011-04-05 15:24 Singa

這樣做的時(shí)間復(fù)雜度是O(n)，可以利用矩陣乘法來(lái)做，把時(shí)間復(fù)雜度降低到O(logn)。回復(fù) 更多評(píng)論

# re: findAnWithDegreeOfTwo(計(jì)算度數(shù)為2的齊次遞歸數(shù)列的第n項(xiàng)) 2011-04-08 10:00 今晚打老虎

@Singa
矩陣乘法么，沒學(xué)過(guò)耶，能指點(diǎn)一下么回復(fù) 更多評(píng)論

# re: findAnWithDegreeOfTwo(計(jì)算度數(shù)為2的齊次遞歸數(shù)列的第n項(xiàng)) 2011-04-11 17:47 Singa

@今晚打老虎
就這個(gè)問(wèn)題的話
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]
上面分別是三個(gè)2*2的矩陣，前兩個(gè)相乘得到第三個(gè)
這樣子就得到一個(gè)類似等比數(shù)列的遞推式了
r1 1
r2 0 類似于公比

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

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

@Singa
感謝指點(diǎn)！回復(fù) 更多評(píng)論

刷新評(píng)論列表

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

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

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

5D空間

留言簿

隨筆分類(18)

文章分類

搜索

積分與排名

最新隨筆

最新評(píng)論

閱讀排行榜

評(píng)論