※ 引述《AmosYang (LetMeGoogleThatForYou)》之銘言： : 解法三則是架構在 : F0 = 1 : F1 = 1 : F(2n-1) = F(n)^2 + F(n-1)^2 : F(2n) = (2 * F(n-1) + F(n)) * F(n) = (F(n-1) + F(n-1) + F(n)) * F(n) : 之上 第一次看到這公式 (以前線代沒認真學 囧) 檢查了一下你的公式， F0, F1 應該是這樣才對 F0 = 0 F1 = 1 : BigInteger.Add BigInteger.Multiply : 解法一 O(n) n=10000 0 : 解法二 O(log n) (4 log n / log 2) = 53 (8 log n / log 2) = 106 : 解法三 O(log n) 47 46 實作了一下解法三 (Top-Down)，數字和你寫的一樣。 來說一下解法 2 的好處吧， 我是用 Bottom-Up 寫的 (1) 首先 T(1) = [ 0 1 ] // 放在 array[0] [ 1 1 ] 接下來一個迴圈算出 T(2) = T(1) * T(1) // * 代表矩陣乘法, 放 array[1] T(4) = T(2) * T(2) // 放 array[2] ... 上面這個動作只需要算一次 (2) 接下來要算 n=10000 時 就可以輕鬆搞定: Matrix result = [1, 1]; // [ f(0), f(1) ] for(int i=0;i<31;i++) if( ((n>>i) & 1) == 1 ) // 判斷第 i 位元是否為 1 result = array[i] * result; 一個 2x2 的矩陣乘法需要 8 個乘法與 4 個加法， 因為 2^13 <= 10000 < 2^14 所以我第一個迴圈就只算到 13 就好。 // 通常我會算到 31 然後因為 10000 的 bit-pattrns 有 4 個 1， 所以需要用到四次的 (2x2 矩陣 乘 2x1 矩陣)， 這種情形乘法需用 4 次 ，加法 2 次。 結論， 乘法次數: 13*8 + 4*4 = 120 加法次數: 13*4 + 4*2 = 60 理論上，只算 n=10000 時，次數應該會更少， 我猜測可能就是你的估計值， 不過我現在的這種作法， 在 n 為其它值時， 只需要重複步驟二即可。 另一個好處就是 code 很短 矩陣相乘: 3 行 步驟(1): 2 行 步驟(2): 3 行 (上面省略了宣告) --- 再補充一下好了， 步驟 (1) 矩陣相乘時，被乘數和乘數都是同一個矩陣 其實只需要用到 7 次乘法。 --- 能不用大腦寫程式是件很開心的事情..XD --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.122.183.196 ※ 編輯: tkcn 來自: 140.122.183.196 (11/04 16:12) ※ 編輯: tkcn 來自: 61.217.194.110 (11/04 19:09)