使用reduce方法的斐波那契数列

于是，我看到有人用reduce方法来计算斐波那契数列。 这是他的想法： (1,0) , (1,1) , (2,1) , (3,2) , (5,3) 对应于 1, 1, 2, 3, 5, 8, 13, 21 ......

代码如下所示

def fib_reduce(n):
    initial =(1,0)
    dummy = range(n)
    fib_n = reduce(lambda prev ,b : (prev[0] + prev[1], prev[0]),
                   dummy,
                   initial)
    
    return fib_n[0]

我明白了(prev[0] + prev[1] , prev[0])这就像a, b = b, b + a。 然而我不明白这是什么b代表 ？

有人可以解释一下吗b?

使用重复应用函数reduce

这个答案 https://stackoverflow.com/a/23795000/3080723建议编写自己的函数repeated重复应用一个函数，而不是调用reduce有一个虚拟的第二个参数。

我们仍然使用reduce，但以更实用的方式并与itertools.repeat.

from itertools import repeat
from functools import reduce

def repeated(func, n):
    def apply(x, f):
        return f(x)
    def ret(x):
        return reduce(apply, repeat(func, n), x)
    return ret

def fibonacci(n):
  get_next_pair = lambda p: (sum(p), p[0])
  first_pair = (1, 0)
  return repeated(get_next_pair, n)(first_pair)[1]

print(fibonacci(0), fibonacci(1), fibonacci(11))
# 0 1 89

使用线性代数重复应用线性函数

功能lambda a,b: b,a+b您想要应用的恰好是一个线性函数。可以用2*2的矩阵来表示。重复将该函数应用于二元素元组与重复将二元素向量乘以矩阵相同。

这很酷，因为使用矩阵的幂比重复应用函数要快得多。

import numpy as np

def fibonacci(n):
  return np.linalg.matrix_power(np.array([[0, 1],[1,1]]), n).dot(np.array([0,1]))[0]

print(fibonacci(0), fibonacci(1), fibonacci(11))
# 0 1 89

如果您不喜欢单行代码，可以将同一函数分解为几行，并使用更明确的变量名称：

import numpy as np

def fibonacci(n):
  next_pair_matrix = np.array([[0, 1],[1,1]])
  matrix_to_the_nth = np.linalg.matrix_power(next_pair_matrix, n)
  first_pair_vector = np.array([0,1])
  nth_pair_vector = matrix_to_the_nth.dot(first_pair_vector)
  return nth_pair_vector[0]

print(fibonacci(0), fibonacci(1), fibonacci(11))
# 0 1 89