作者tkcn (小安)
看板java
标题Re: Fibonacci number
时间Wed Nov 4 17:09:21 2009
※ 引述《tkcn (小安)》之铭言：
: 再补充一下好了，
: 步骤 (1) 矩阵相乘时，被乘数和乘数都是同一个矩阵
: 其实只需要用到 7 次乘法。
确实如 jlovet 所说，
f(n-1) f(n)
f(n) f(n+1)
此种型式的矩阵相乘(平方)，
只需要 4 次乘法与 3 次加法
因此 f(10000) 使用 bottom-up，
乘法次数为: 13*4 + 4*4 = 68
加法次数为: 13*3 + 4*2 = 47
呼，这样应该有帮 Q-matrix 平反了吧
--
有时候真的觉得大学时没参加到 ICPC 还蛮可惜的...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.122.183.196
1F：→ jlovet:而且每次还可以顺便算隔壁的...很划算低 11/04 17:45
2F：推 costbook:这算是动态规划法吗？ 11/04 18:35
3F：→ tkcn:是的 11/04 18:38
4F：→ AmosYang:题外话:如果要拼F0到Fn全算的话，我 猜 解法一会大胜 XD 11/05 10:56
5F：→ tkcn:这是当然..解法一只需要乘 n-1 次 11/05 10:58
6F：→ AmosYang:不过不知道实际上 BigInteger 的加与乘的影响有多大... 11/05 11:27
7F：→ AmosYang:(懒得去翻src出来看了) ICPC没玩到，可以玩 topcoder.com 11/05 11:29