: → jlovet:嗯,我觉得不知道fibonacci 可以在log N算出来的人蛮可怜的 11/03 14:48 : → SansWord:好跳tone的感觉..fibonacci怎麽样在log N算出来？(好奇) 11/04 02:30 : 推 AmosYang:大学linear algebra应该会教到…可以推出 F(2n)=F(n)+F(n 11/04 09:02 : → AmosYang:重推一次: F(2n-1) = F(n)^2+F(n-1)^2 11/04 09:04 : → AmosYang:hmm...其实 wikipedia 上有; search for "matrix form" 11/04 09:06 : → AmosYang: http://en.wikipedia.org/wiki/Fibonacci_number 11/04 09:07 : → tkcn:http://www.csie.ntnu.edu.tw/~u91029/Q-matrix.html 11/04 10:43 刚胡思乱想了一下…发现件蛮有趣的事 如果把 BigInteger 的乘法与加法的代价也算进来， tkcn 指出的 Q-matrix 算法不见得占优势…以下是我的分析 解法一: 普通解法，开一个 array, 从 F0 开始填，一路填到 Fn 演算法本身是 O(n); 实际上做了 O(n) 次 BigInteger 的加法 这解法的好处是简单易写，且算过一次就不用再算，以後可以直接查表 解法二: Q-matrix 演算法号称为 O(log n) 之所以用号称这字眼是因为我自己还没有推演求证过 但 2x2 的 matrix 相乘事实上做了 8 次 BigInteger 乘法及 4 次 BigInteger 加法 matrix 相乘 n 次就是做了 8n 次 BigInteger 乘法及 4n 次 BigInteger 加法 当然，matrix 相乘还可以再优化，不过，我觉得在比赛的压力下实在很难办到 XD smartboy 那种神人可以，我是办不到的 XD 解法二稍为在 matrix 里加工一下，一样可以存放已经算过的值 解法三为解法一的变型 解法一是架构在 F0 = 1 F1 = 1 Fn = F(n-1) + F(n-2) 之上 解法三则是架构在 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) 之上 一样开一个 array 存放算过的值 演算法看起来是 O(log n) 这部分我还没有仔细去推演，但用实际数值算出来的结果， F100 要算 16 次; 而 F10000 要算 33 次，我就当他是 O(log n) 了 XD F100 要做 21 次 BigInteger 加法及 21 次 BigInteger 乘法 F10000 要做 47 次 BigInteger 加法及 46 次 BigInteger 乘法 解法三的写法与解法一一样很直接，然而，这个解法是要看运气的， 因为坦白说在比赛的现场压力下我是没办法从解法二一路推演到解法三 XD 与其去推演这个不如去用解法一硬干 XD 总结，假设要求 F10000 BigInteger.Add BigInteger.Multiply 解法一 O(n) 10000 0 解法二 O(log n) 40000 80000 解法三 O(log n) 47 46 这样子比较，个人感觉上解法二有点吃力不讨好 不过，这个分析还没考虑到 BigInteger 实做的方式及大小数字计算的速度差异… 待有心人三种解法都写一次，开 profiler 直接去量时间吧... XD --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 65.87.177.87 突然想到，其实在 2x2 的 matrix multiplication 运算里， 可以很简单地用 dynamic programming 来优化 所以事实上解法二没有我想像的那麽糟… 待别的有心人来为解法二平反吧 Z..z..z... ※ 编辑: AmosYang 来自: 65.87.177.87 (11/04 13:11) 突然又再想到…解法二的 matrix multiplication 用最简单的 A^m * A^n = A^(m+n) 优化後，就会变成 BigInteger.Add BigInteger.Multiply 解法一 O(n) 10000 0 解法二 O(log n) 400 800 解法三 O(log n) 47 46 不过，这个表格只是比较 "求一个数字" 的代价 解法二、三看起来代价比较小，也只是取巧 真的碰上测试资料要 F0 到 Fn 通通问一遍的，解法二、三大概也占不了什麽便宜 XD 最後…还是岸和田那句老话: 实验最准!! 不用代入公式!! 也不用修正误差!! XD Zzz... ※ 编辑: AmosYang 来自: 65.87.177.87 (11/04 13:24) 快要睡着时再突然想到…修正解法二的数字… 之前的 400 与 800 毫无根据…不知道为什麽会那样想… 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 至此…其实解法二、三没差多少了… 今夜独角戏到此结束…谢谢收看… Zzz... ※ 编辑: AmosYang 来自: 65.87.177.87 (11/04 13:52) ※ 编辑: AmosYang 来自: 65.87.177.87 (11/04 13:55) 我一开始是用 C++ ，後来被 BigInteger 引去 Java 再後来在 TopCoder.com 上见识到 C# 的流氓之处，就再转 C# 了 现在则是用嘴吧写… XD 刚有偷看底下的回文…的确不需要乘到 8 次，多谢指教 :D ※ 编辑: AmosYang 来自: 65.87.177.87 (11/05 10:25)