※ 引述《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)