应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » Java » 矩阵快速幂计算斐波拉契级数第N项的值
41/1返回列表
查看: 545  |  回复: 3
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

etdeng

银虫 (初入文坛)

[求助] 矩阵快速幂计算斐波拉契级数第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的回帖

王者归来.

木虫 (职业作家)

【答案】应助回帖

感谢参与，应助指数 +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 的主题更新
41/1返回列表
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 一志愿吉林大学材料学硕321求调剂 +4 Ymlll 2026-03-18 6/300 2026-03-18 22:15 by li123456789.
[考研] 354求调剂 +4 Tyoumou 2026-03-18 7/350 2026-03-18 21:45 by Tyoumou
[考研] 267一志愿南京工业大学0817化工求调剂 +8 SUICHILD 2026-03-12 8/400 2026-03-18 20:55 by winsuccess
[考研] 【同济软件】软件（085405）考研求调剂 +3 2026eternal 2026-03-18 3/150 2026-03-18 19:09 by 搏击518
[考研] 一志愿武理材料305分求调剂 +5 想上岸的鲤鱼 2026-03-18 6/300 2026-03-18 17:53 by 无际的草原
[考研] 化学工程321分求调剂 +15 大米饭！ 2026-03-15 18/900 2026-03-18 14:52 by haxia
[考研] 314求调剂 +8 无懈可击的巨人 2026-03-12 8/400 2026-03-18 14:50 by haxia
[考研] 08工科 320总分 求调剂 +5 梨花珞晚风 2026-03-17 5/250 2026-03-18 14:49 by haxia
[考研] 280求调剂 +6 咕噜晓晓 2026-03-18 7/350 2026-03-18 11:25 by 无际的草原
[考博] 26博士申请 +3 1042136743 2026-03-17 3/150 2026-03-17 23:30 by 轻松不少随
[考研] 268求调剂 +7 好运连绵不绝 2026-03-12 8/400 2026-03-17 20:28 by xilongliang
[考研] 277调剂 +5 自由煎饼果子 2026-03-16 6/300 2026-03-17 19:26 by 李leezz
[考研] 材料专硕326求调剂 +6 墨煜姒莘 2026-03-15 7/350 2026-03-17 17:10 by ruiyingmiao
[考研] 材料工程专硕274一志愿211求调剂 +6 薛云鹏 2026-03-15 6/300 2026-03-17 11:05 by 学员h26Tkc
[考研] 东南大学364求调剂 +5 JasonYuiui 2026-03-15 5/250 2026-03-16 21:28 by 木瓜膏
[考研] 297一志愿上交085600求调剂 +5 指尖八千里 2026-03-14 5/250 2026-03-14 17:26 by a不易
[考研] ［0860］321分求调剂，ab区皆可 +4 宝贵热 2026-03-13 4/200 2026-03-13 22:01 by 星空星月
[考研] 311求调剂 +3 冬十三 2026-03-13 3/150 2026-03-13 20:41 by JourneyLucky
[考研] 一志愿山大07化学 332分 四六级已过 本科山东双非 求调剂！ +3 不想理你 2026-03-12 3/150 2026-03-13 14:18 by JourneyLucky
[考研] 333求调剂 +3 152697 2026-03-12 4/200 2026-03-13 07:08 by Iveryant
信息提示
关闭
请填处理意见
关闭