24小时热门版块排行榜    

查看: 490  |  回复: 3

etdeng

银虫 (初入文坛)

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

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

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

用普通方法,计算100以内还是很快的。
如果考虑算法的时间效率,计算10000呢?请大神们用java提供一种快速的算法
求教高手。
回复此楼
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

王者归来.

木虫 (职业作家)

【答案】应助回帖

感谢参与,应助指数 +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

木虫 (小有名气)

【答案】应助回帖

矩阵快速幂。
令二维矩阵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的回帖

rbs

木虫 (小有名气)

【答案】应助回帖

矩阵B应是
| F2 |
| F1 |
4楼2015-04-03 15:03:48
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 etdeng 的主题更新
信息提示
请填处理意见