24小时热门版块排行榜    

Znn3bq.jpeg
查看: 556  |  回复: 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

木虫 (小有名气)

【答案】应助回帖

矩阵B应是
| F2 |
| F1 |
4楼2015-04-03 15:03:48
已阅   回复此楼   关注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

木虫 (小有名气)

【答案】应助回帖

矩阵快速幂。
令二维矩阵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的回帖
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 277 数一104,学硕,求调剂 +17 瓶子PZ 2026-04-09 18/900 2026-04-10 22:47 by 来看流星雨10
[考研] 281求调剂 +9 觉得好的吧 2026-04-10 9/450 2026-04-10 22:16 by 猪会飞
[考研] 本9一志愿2 0854低分专硕286求调剂 +10 芒种111 2026-04-04 10/500 2026-04-10 12:31 by luosha500
[考研] 求调剂 +16 熊二想上岸 2026-04-04 16/800 2026-04-10 11:24 by may_新宇
[考研] 调剂申请086000一志愿西北农林科技大学生物与医药320分-本科齐鲁工业大学 +3 美美女士 2026-04-09 3/150 2026-04-10 10:31 by liuhuiying09
[考研] 297求调剂 +27 GENJIOW 2026-04-07 30/1500 2026-04-09 23:20 by wolf97
[考研] 269电子信息求调剂,可转专业 +9 独酌wl 2026-04-06 9/450 2026-04-09 20:55 by laoshidan
[考研] 269求调剂 +7 跪求收留。 2026-04-04 7/350 2026-04-09 19:06 by 探123
[考研] 材料调剂 +14 一样YWY 2026-04-06 14/700 2026-04-08 23:00 by 猪会飞
[考研] 专硕310求调剂 +7 捞捞我…. 2026-04-04 8/400 2026-04-08 20:24 by yutian743
[考研] 293分求调剂,外语为俄语 +7 加一一九 2026-04-07 10/500 2026-04-08 20:14 by yutian743
[考研] 材料科学与工程320求调剂,080500 +12 黄瓜味薯片 2026-04-06 12/600 2026-04-08 16:26 by luoyongfeng
[考研] 调剂求助(生物与医药) +6 @6952 2026-04-06 6/300 2026-04-07 23:52 by lys0704
[考研] 277、学硕,求调剂 数一104, +11 瓶子PZ 2026-04-07 12/600 2026-04-07 23:30 by 一只好果子?
[考研] 277求调剂 数一104分 +9 瓶子PZ 2026-04-05 14/700 2026-04-07 17:52 by 蓝云思雨
[考研] (调剂)一志愿报考哈尔滨工业大学0857资源与环境专业378分考生 +7 狠狠加油 2026-04-05 8/400 2026-04-06 16:52 by momo皓
[考研] 复试调剂 +5 asdasdassda 2026-04-05 5/250 2026-04-06 09:32 by dongzh2009
[考研] 331求调剂 +8 于征yz 2026-04-05 8/400 2026-04-06 00:54 by fmesaito
[考研] 材料调剂 +14 壹贰贰亿 2026-04-04 14/700 2026-04-05 23:31 by 来看流星雨10
[考研] 考研调剂 +11 小sun要好运 2026-04-04 11/550 2026-04-05 08:02 by qlm5820
信息提示
请填处理意见