斐波那契数列使用归约法 [英] Fibonacci sequence using reduce method

问题描述

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

So, I saw someone using the reduce method to calculate the Fibonacci sequence. Here is his idea: (1,0) , (1,1) , (2,1) , (3,2) , (5,3) corresponds to 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代表什么?

I understand the (prev[0] + prev[1] , prev[0]) which is like a, b = b, b + a. However, I don't understand what this b stands for ?

有人可以解释一下b吗?

推荐答案

反复使用reduce

应用函数

此答案建议编写自己的函数repeated以重复应用函数，而不是调用reduce带有第二个伪参数.

Repeatedly applying a function using reduce

This answer suggests writing up your own function repeated to repeatedly apply a function, rather than calling reduce with a dummy second argument.

我们仍然使用reduce，但功能更强大，并且使用itertools.repeat.

We still use reduce, but in a more functional manner and with 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矩阵表示.将该函数重复应用于两个元素的元组与将两个元素的向量重复乘以该矩阵相同.

Repeatedly apply a linear function using linear algebra

The function lambda a,b: b,a+b which you want to apply happens to be a linear function. It can be represented by a 2*2 matrix. Repeatedly applying the function to a two-element tuple is the same as repeatedly multiplying a two-element vector by the matrix.

这很酷，因为采用矩阵的功效比重复应用函数要快得多.

This is cool, because taking the power of a matrix is much, much faster than repeatedly applying a function.

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

如果您不喜欢单行代码，则此函数分解为几行，并使用更明确的变量名:

If you don't like one-liners, here is the same function decomposed on a few lines with more explicit variable names:

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

这篇关于斐波那契数列使用归约法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！