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 今晚打老虎 阅读(1006) 评论(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
感谢指点！  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理