Python高阶函数:求Fibonacci数的新方法

Question

给了我一个问题来写一个高阶函数来求fibonacci数。首先，我在下面定义了combine函数：

def combine(f, op ,n):
    result = f(0)
    for i in range(n):
        result = op(result, f(i))
return result

例如，new_fib(10) = 55

因此，我应该定义的函数是找到第n个fibonacci数：

def new_fib(n):
    def f(x):
        ...
    def op(x, y):
        ...
    return combine(f, op, n+1)

我必须解决这个问题的想法是将斐波纳契序列放入f(x)函数中，但是我一直面临很多问题。我现在拥有的是：

def new_fib(n):
    def op(x,y):
        return x+y
    def f(x):
        a,b = 0, 1
        fibs = ()
        for i in range(n+1):
            a, b = b, a+b
            fibs += (a,)
        return fibs[x]
    return combine(f, op, n+1)

但这是错误的，因为它积累得太快了。我能想象出为什么会出现在我的脑海中，但我想不出一条出路来绕过它。有人有什么建议吗？非常感谢！谢谢!

Answer 1

操作应该是a, b => b, a+b，您可以迭代它。

代码可以是：

def new_fib(n):
    def op(a, b):
        return b, a+b
    def combine(initial, op, n):
        a, b = initial
        for i in range(n):
            a, b = op(a, b)
        return b
    if n == 0:                # special processing for 0 and 1
        return 0
    if n == 1:
        return 1
    return combine((0,1), op, n - 1)

它正确地给出了55的new_fib(10)