24小时热门版块排行榜

返回列表

etdeng

银虫 (初入文坛)

应助: 0 (幼儿园)
金币: 304.5
帖子: 31
在线: 26.8小时
虫号: 2925970
注册: 2014-01-11
专业: 教育技术学

[求助] 矩阵快速幂计算斐波拉契级数第N项的值已有2人参与

矩阵快速幂计算斐波拉契级数第N项的值，与用递推法求解，分别写出程序，比较算法效率。

编制一段程序，计算斐波拉契级数第N项的值。
斐波那契级数：f(0)=0;f(1)=1;
当n>1时，f(n)=f(n-1)+f(n-2)

用普通方法，计算100以内还是很快的。
如果考虑算法的时间效率，计算10000呢？请大神们用java提供一种快速的算法
求教高手。

回复此楼

» 猜你喜欢

1楼 2014-12-17 19:42:17

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

王者归来.

木虫 (职业作家)

应助: 17 (小学生)
金币: 4014.3
红花: 4
帖子: 3802
在线: 117.6小时
虫号: 3542982
注册: 2014-11-17
性别: GG
专业: 经济学

【答案】应助回帖

感谢参与，应助指数 +1

这个是幂法。(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}

然后建议你看一下斐波那契数列的百度百科，里面给了几个它的特性公式，估计可以给你提高计算效率

[ 发自手机版 http://muchong.com/3g ]

赞一下

回复此楼

2楼2014-12-19 03:43:08

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

rbs

木虫 (小有名气)

应助: 32 (小学生)
金币: 3589.1
红花: 3
帖子: 221
在线: 16.3小时
虫号: 695603
注册: 2009-02-03
性别: GG
专业: 计算机应用技术

【答案】应助回帖

矩阵快速幂。
令二维矩阵A为：
| 1 1 |
| 0 1 |
列矩阵B为：
| F1 |
| F2 |

则A乘B得：
| F1 + F2 |  也就是  | F3 |
| F2       |          | F2 |

所以计算  A^n * B，就能得到F(n+2)。而A的n次方可以使用矩阵快速幂在对数时间求得。

赞一下

回复此楼

3楼2015-04-03 15:02:52

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖