24小时热门版块排行榜    

Znn3bq.jpeg
查看: 553  |  回复: 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 的主题更新
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 本9 一志愿西工大085601 324求调剂 +5 wysyjs25 2026-04-10 5/250 2026-04-10 16:57 by luoyongfeng
[考研] 343求调剂 +5 王国帅 2026-04-10 5/250 2026-04-10 16:56 by 猪会飞
[考研] 一志愿211,化学学硕,310分,本科重点双非,求调剂 +27 努力奋斗112 2026-04-07 30/1500 2026-04-10 15:06 by Kilig0317
[考研] 求调剂 +9 翩翩一书生 2026-04-09 9/450 2026-04-10 11:43 by wp06
[考研] 材料复试求调剂 +20 xhhdjdjsjks 2026-04-09 20/1000 2026-04-10 10:25 by 孙小小12457
[考研] 材料专硕调剂 +16 哈哈哈吼吼吼哈 2026-04-07 17/850 2026-04-09 21:16 by wutongshun
[考研] 086003调剂求助 +19 苏弋万 2026-04-09 20/1000 2026-04-09 20:48 by bljnqdcc
[考研] 289求调剂 +4 L1ttleTiger 2026-04-04 4/200 2026-04-09 19:53 by xiayizhi
[考研] 材料调剂 +10 18815505510 2026-04-09 11/550 2026-04-09 17:07 by 544594351
[考研] 求调剂,262机械专硕 +6 嗯yyl 2026-04-08 6/300 2026-04-09 12:01 by zhouyuwinner
[考研] 一志愿郑州大学085600求调剂 +21 吃的不少 2026-04-05 24/1200 2026-04-08 16:47 by sunhuadong
[考研] 277、学硕,求调剂 数一104, +11 瓶子PZ 2026-04-07 12/600 2026-04-07 23:30 by 一只好果子?
[考研] 生物工程求调剂 +13 喜欢还是不甘心 2026-04-05 13/650 2026-04-07 16:55 by Ecowxq666!
[考研] 一志愿9材料学硕297已过六级求调剂推荐 +11 adaie 2026-04-04 12/600 2026-04-05 19:04 by 蓝云思雨
[考研] 313求调剂 +5 海日海日 2026-04-04 7/350 2026-04-05 13:58 by imissbao
[考研] 353求调剂 +10 MayUxw1 2026-04-03 10/500 2026-04-05 09:23 by 无际的草原
[考研] 313求调剂 +3 海日海日 2026-04-04 3/150 2026-04-05 07:48 by 544594351
[考研] 一志愿沪985,326分求调剂 +3 刘墨墨 2026-04-03 3/150 2026-04-04 11:16 by 悲伤的芋头
[考研] 学硕288调剂!!! +3 小王xw123 2026-04-03 3/150 2026-04-03 21:20 by 啵啵啵0119
[考研] 294求调剂 +6 Grey_Ey 2026-04-03 6/300 2026-04-03 20:46 by 欣喜777
信息提示
请填处理意见