先甩一个在线练习的地址：牛客网
题目描述
给出一个整数 n，请输出斐波那契数列的第 n 项对 1e9 + 7 取模的值。
斐波那契数列的前几项（从第0项开始）为：[0, 1, 1, 2 ,3 ,5 ,8 ,13, ...]
n的取值范围：1 <= n <= 1e18，且有4秒和512MB内存的限制。
题目的原标题为
斐波那契数列问题的 递归 和 动态规划
这个标题实际上存在着一定的误导性。
递归解法的主要思路是直接套用F(n) = F(n-1) + F(n-2)这个公式，将F(n)拆分为多个1按一定顺序相加，时间复杂度为O(F(n))。动态规划的主要思路是保存F(1), F(2), ..., F(n-1)的值，使得每次计算F(k)的时候都只需要做一次加法运算，时间复杂度为O(n)。
但是这里n的取值范围较大，既不可能存储所有的F(k)，也来不及把它们全部计算一遍，因此需要一种时间复杂度小于O(n)，最好为O(log(n))甚至O(1)的解法。
那么自然而然就会产生两种思路：
- 借助
F(k)及其附近的几个值来表示F(2k)和F(2k+1)， - 借助
F(1), F(2), F(4), F(8), ...等值来表示F(k)。
后一种思路我没想到具体应该如何实施，这里直接复制别人的说法：
f(n) = f(n-1) + f(n-2)
f(n-1) = f(n-1)
矩阵：
[ f(n) ] = [ 1*f(n-1) + 1*f(n-2) ] = [ 1 1 ] * [ f(n-1) ]
[ f(n-1) ] [ 1*f(n-1) + 0*f(n-2) ] [ 1 0 ] [ f(n-2) ]
显然：
[ f(2) ] = [ 1 ]
[ f(1) ] [ 1 ]
假设：
mul = [[ 1, 1 ], [ 1, 0 ]]
那么：
[ f(n), f(n-1) ]T
= mul * [ f(n-1), f(n-2) ]T
= mul * mul * [ f(n-2), f(n-3) ]T
= ...
= mul^(n-2) * [ f(2), f(1) ]T
转变为快速幂问题：
快速求 mul^(n-2) 的值即可
快速求有限大小矩阵的n次幂问题显然是动态规划，且时间和空间复杂度均为O(log(n))，具体编码留作练习。
反正我拿到题目就直接顺着第一种思路想下去了：
f(k) = f(k-1) + f(k-2) = f(k-2) + f(k-3) + f(k-2)
= 2f(k-2) + f(k-3) = 2*(f(k-3) + f(k-4)) + f(k-3)
= 3f(k-3) + 2f(k-4) = 3*(f(k-4) + f(k-5)) + 2f(k-4)
= 5f(k-4) + 3f(k-5) = ...
= f(a+1) * f(k-a) + f(a) * f(k-a-1) for a in range(1,k-1)
f(2k+1) = f(k) * f(k) + f(k+1) * f(k+1)
f(2k) = f(k) * (f(k-1) + f(k+1))
因此也可以借助递归和动态规划的思路，只求解f(n/2)附近的2--3个值，f(n/4)附近的3--4个值，f(n/8)附近的3--4个值……且这些值可以由小到大依次求出，整个算法的时间和空间复杂度均为O(a*log(n))，其中a的数量级不会太高，可能在O(1)到O(log(n))之间，但我不会证明。。。手动捂脸。
由于不知道在线练习/笔试的环境能否使用NumPy等库，于是手写了一个最简单的稀疏一维列表class，其中又手写了一个折半查找法，于是又是连编码带debug一个晚上过去了。。。
上最终代码：
import os
M = 10 ** 9 + 7
def add_mod(a, b):
r = a + b
if r < 0 or r >= M:
r = r % M
return r
def mul_mod(a, b):
r = a * b
if r < 0 or r >= M:
r = r % M
return r
class SparseList():
indices = []
data = []
def __init__(self, ls):
self.indices = [0, ]
self.data = [ls, ]
def _binary_search(self, data, fromlist):
if l <= 1:
return 0
l2 = l // 2
if data < fromlist[l2]:
r = self._binary_search(data, fromlist[:l2])
else:
r = l2 + self._binary_search(data, fromlist[l2:])
return r
def get(self, idx):
indices_idx = self._binary_search(idx, self.indices)
idx_offset = idx - self.indices[indices_idx]
if idx_offset >= len(self.data[indices_idx]):
raise IndexError
else:
return self.data[indices_idx][idx_offset]
def put(self, idx, dt): # set value
indices_idx = self._binary_search(idx, self.indices)
idx_offset = idx - self.indices[indices_idx]
l = len(self.data[indices_idx])
if idx_offset > l:
indices_idx_1 = indices_idx + 1
if indices_idx_1 < len(self.indices)
and idx == self.indices[indices_idx_1] - 1:
self.indices[indices_idx_1] = idx
self.data[indices_idx_1].insert(0, dt)
else:
self.indices.insert(indices_idx_1, idx)
self.data.insert(indices_idx_1, [dt,])
elif idx_offset == l:
self.data[indices_idx].append(dt)
else:
self.data[indices_idx][idx_offset] = dt
def toString(self):
return '[%s]' % (
', '.join(
['%d: %s' % (i, str(j))
for i,j in zip(self.indices, self.data)
]
)
)
def pretty(self):
return ('[%s' + os.linesep + ']') % (
(',' + os.linesep + ' ').join(
['%d: %s' % (i, str(j))
for i,j in zip(self.indices, self.data)
]
)
)
class FiboMod():
data = SparseList([0, 1, 1, 2 ,3 ,5 ,8 ,13, 21, 34, 55, 89])
def fibo_mod_no_data(self, n):
try:
return self.data.get(n)
except IndexError:
(a, b, c) = (0, n // 2, n % 2)
if c:
c += b
(b, c) = tuple(self.fibo_mod_no_data(i) for i in [b, c])
r = add_mod(mul_mod(b, b), mul_mod(c, c))
else:
(a, c) = (b - 1, b + 1)
(a, b, c) = tuple(self.fibo_mod_no_data(i) for i in [a, b, c])
r = mul_mod(b, add_mod(a, c))
self.data.put(n, r)
return r
FIBO = FiboMod()
def main():
n = int(input().rstrip().split()[0])
print(FIBO.fibo_mod_no_data(n))
if __name__ == '__main__':
main()
启示：
- 思考一个好的算法，比一有想法就编码更好。
- 有了想法一定要编码，不要眼高手低，不然连折半查找都写不对，即使以前写的同一段代码没有任何问题且工作良好。
2021-06-07更新：
折半查找这么常见/常用的算法，Python当然是有相应的库的，也就是bisect：
https://docs.python.org/2.7/library/bisect.html
于Python 2.1中新增，提供以下方法：
-
bisect.bisect_left(a, x, lo=0, hi=len(a))
假定列表a是有序的，在a[lo:hi]中查找并返回一个下标i，使得a.insert(i, x)后仍然有序，且当x == a[i]时，x被插入到原有元素的左侧。 -
bisect.bisect_right(a, x, lo=0, hi=len(a))
与bisect_left类似，但是当x == a[i]时，x被插入到原有元素的右侧。 -
bisect.insort_left(a, x, lo=0, hi=len(a))
消耗O(log(n))时间执行bisect_left，然后消耗O(n)时间插入元素x，使a[lo:hi]保持有序。 -
bisect.insort_right(a, x, lo=0, hi=len(a))
与insort_left类似，但是当x == a[i]时，x被插入到原有元素的右侧。
