作者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
→ jlovet:而且每次還可以順便算隔壁的...很划算低 11/04 17:45
推 costbook:這算是動態規劃法嗎？ 11/04 18:35
→ tkcn:是的 11/04 18:38
→ AmosYang:題外話:如果要拼F0到Fn全算的話，我 猜 解法一會大勝 XD 11/05 10:56
→ tkcn:這是當然..解法一只需要乘 n-1 次 11/05 10:58
→ AmosYang:不過不知道實際上 BigInteger 的加與乘的影響有多大... 11/05 11:27
→ AmosYang:(懶得去翻src出來看了) ICPC沒玩到，可以玩 topcoder.com 11/05 11:29