5D空间
学习总结与经验交流
::
首页
::
新随笔
::
联系
::
聚合
::
管理
::
留言簿
给我留言
查看公开留言
查看私人留言
随笔分类
(18)
解题报告
(rss)
困难与疑问(3)
(rss)
思考中
(rss)
我的开源库(5)
(rss)
学习笔记(10)
(rss)
文章分类
5DC++
(rss)
转载与分享
(rss)
搜索
积分与排名
积分 - 17926
排名 - 869
最新随笔
1. C++中对浮点数的格式化显示
2. PointerPool(指针池)
3. 类型转换操作符
4. VS2010实用小记
5. 关于二重模板 小记1
6. 模板的声明与实现的分离方法
7. 多重继承、二义性、虚基类(虚继承)之我见
8. LHRODT(非递归求解度数为2的线性齐次方程的第n项)
9. 类实例化时 默认构造函数调用 小记
10. probability(概率发生器)
11. findAnWithDegreeOfTwo(计算度数为2的齐次递归数列的第n项)
12. Zeller(计算某一天是星期几)
13. 【求助】如何在继承中隐藏基类的某些公共接口?
14. 【求助】如何限制模板接受的类型?
15. 关于类模板的友元函数
最新评论
1. re: 【求助】如何在继承中隐藏基类的某些公共接口?
评论内容较长,点击标题查看
--wjq
2. re: 【求助】如何在继承中隐藏基类的某些公共接口?
在派生类中使用using关键字,在private中声明基类你想隐藏的公共接口就可以了。
--wjq
3. re: 多重继承、二义性、虚基类(虚继承)之我见
可以啊,自慰.@自己继承自己
--CL
4. re: 多重继承、二义性、虚基类(虚继承)之我见
孩子,代码打错了。
class C : public C
自己继承自己?
--自己继承自己
5. re: probability(概率发生器)
逗号 表达式
从左到右计算,然后只取最后一个值....
--egmkang
阅读排行榜
1. 多重继承、二义性、虚基类(虚继承)之我见(3374)
2. 模板的声明与实现的分离方法(2104)
3. PointerPool(指针池)(1802)
4. probability(概率发生器)(1442)
5. 关于二重模板 小记1(1296)
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
今晚打老虎
阅读(1012)
评论(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
感谢指点!
回复
更多评论
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
PointerPool(指针池)
LHRODT(非递归求解度数为2的线性齐次方程的第n项)
probability(概率发生器)
findAnWithDegreeOfTwo(计算度数为2的齐次递归数列的第n项)
Zeller(计算某一天是星期几)
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 今晚打老虎