Fibonacci数计算中的两个思维盲点及其扩展数列的通用高效解法.pdfVIP

Fibonacci 数计算中的两个思维盲点及其扩展数列的通用高效解法 /flyinghearts /flyinghearts /flyinghearts ㈠ Fibonacci 数 刚接触Fibonacci 数的时候，在网上看到“矩阵法”，看到要先实现一个矩阵乘法，感觉 太麻烦了。后来仔细观察Fibonacci 数列，发现有下面的规律： F(n) = F(k)*F(n+1-k) + F(k-1)*F(n-k) = F(2*n) = F(n+1) * F(n) + F(n) * F(n - 1) F(2*n+1) = F(n+1) * F(n+1) + F(n) * F(n) 根据该公式：要计算F(n)，只需先计算出F(n/2)和F(n/2+1)，于是得出一个数的O(logn) 解法。（例如：计算F(13)= 计算F(6)、F(7)= 计算F(3)、F(4)= 计算F(1)、F(2)。） 再后来无意间发现，“矩阵法”根本就不必实现一个矩阵，网上广为流传的糟糕的做法，掩 盖了“矩阵法”的优美。 先回顾下Fibonacci数列的矩阵法： F(n + 2) F(n +1) 1 1 F(n +1) F(n) 1 1 n F(2) F(1) ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ = ... = ⎜ ⎟ ⎜ ⎟ (1) ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝F(n +1) F(n) ⎠ ⎝1 0⎠ ⎝F(n) F(n - 1)⎠ ⎝1 0⎠ ⎝F(1) F(0) ⎠ F(n +1) 1 1 F(n) 1 1 n F(1) ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ = ... = ⎜ ⎟ ⎜ ⎟ (2) ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ F(n) ⎠ ⎝1 0⎠ ⎝F(n -1) ⎠ ⎝1 0⎠ ⎝F(0) ⎠ 上式中，对系数矩阵A求n次方，有O(log n)解法，因而整个算法是O(log n)。 某些介绍矩阵法的文章，会“偷懒”采用上面的第二种写法，而不是第一种写法。偷懒 的结果，总是要付出代价的。对上面矩阵法的实现，存在两个盲点，也正由于这两个盲点， 使“矩阵法”的实现代码看起来很复杂，失去了简洁之美。 盲点之一：对系数矩阵A求n次方，可以不采用矩阵乘法来实现。 将F(1) = F(2) = 1， F(0) = 0代入上面的公式1，得到： n+1 ⎛F(n + 2) F(n +1)⎞ ⎛1 1 ⎞ ⎜ ⎟ = ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎝F(n +1) F(n) ⎠ ⎝1 0⎠ ⎛1 1 ⎞n ⎛F(n +1) F(n) ⎞ ⎛a1 +a2 a1 ⎞ ⎜ ⎟ = ⎜ ⎟ = ⎜ ⎟ (其中a1 = F(n), a2 = F(n -1)) ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝1 0⎠ ⎝F(n) F(n -1) ⎠ ⎝a1