24小时热门版块排行榜    

查看: 548  |  回复: 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的回帖

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的回帖
查看全部 4 个回答

王者归来.

木虫 (职业作家)

【答案】应助回帖

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

木虫 (小有名气)

【答案】应助回帖

矩阵B应是
| F2 |
| F1 |
4楼2015-04-03 15:03:48
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 0703化学 305求调剂 +4 FY_yy 2026-03-14 4/200 2026-03-19 05:54 by anny19840123
[考研] 求材料调剂 +8 隔壁陈先生 2026-03-12 8/400 2026-03-18 22:19 by li123456789.
[考研] 330求调剂 +3 小材化本科 2026-03-18 3/150 2026-03-18 21:55 by 无懈可击111
[考研] 274求调剂 +5 S.H1 2026-03-18 5/250 2026-03-18 21:27 by guosr9609
[考研] 一志愿天津大学化学工艺专业(081702)315分求调剂 +10 yangfz 2026-03-17 10/500 2026-03-18 20:14 by walc
[考研] 314求调剂 +8 无懈可击的巨人 2026-03-12 8/400 2026-03-18 14:50 by haxia
[考研] 0703化学调剂 +4 pupcoco 2026-03-17 7/350 2026-03-18 12:14 by djl2006
[考研] 环境工程调剂 +8 大可digkids 2026-03-16 8/400 2026-03-18 09:36 by zhukairuo
[考博] 26博士申请 +3 1042136743 2026-03-17 3/150 2026-03-17 23:30 by 轻松不少随
[考研] 085600材料与化工求调剂 +5 绪幸与子 2026-03-17 5/250 2026-03-17 16:40 by laoshidan
[考研] 290求调剂 +3 p asserby. 2026-03-15 4/200 2026-03-17 16:35 by wangkm
[考研] 考研调剂 +3 淇ya_~ 2026-03-17 5/250 2026-03-17 09:25 by Winj1e
[基金申请] 今年的国基金是打分制吗? 50+3 zhanghaozhu 2026-03-14 3/150 2026-03-16 17:07 by 北京莱茵润色
[考研] 318求调剂 +3 Yanyali 2026-03-15 3/150 2026-03-16 16:41 by houyaoxu
[考研] 070300化学学硕求调剂 +6 太想进步了0608 2026-03-16 6/300 2026-03-16 16:13 by kykm678
[考研] 0856求调剂 +3 刘梦微 2026-03-15 3/150 2026-03-16 10:00 by houyaoxu
[考研] 材料工程调剂 +9 咪咪空空 2026-03-12 9/450 2026-03-13 22:05 by 星空星月
[考研] 304求调剂 +7 7712b 2026-03-13 7/350 2026-03-13 21:42 by peike
[考研] 307求调剂 +5 超级伊昂大王 2026-03-12 5/250 2026-03-13 15:56 by 棒棒球手
[考研] 工科材料085601 279求调剂 +8 困于星晨 2026-03-12 10/500 2026-03-13 15:42 by ms629
信息提示
请填处理意见