封闭形式斐波那契系列 [英] Closed form Fibonacci Series

问题描述

我使用Python使用以下公式创建斐波纳契：

I am using Python to create a Fibonacci using this formula:

我有这个递归的Fibonacci函数：

I have this recursive Fibonacci function:

def recursive_fibonacci(n):
if n <= 1:
    return int((((1 / (5 ** 0.5)) * (1 + (5 ** 0.5))) ** n) - (((1 / (5 ** 0.5)) * (1 - (5 ** 0.5))) ** n))
else:
    return(recursive_fibonacci(n - 1) + recursive_fibonacci(n - 2))

要显示它我使用的是：

nterms = 10

if nterms <= 0:
    print("Please Enter a positive integer")
else:
    print("Recursive Fibonacci Sequence: " ,
        [recursive_fibonacci(i) for i in range(nterms)])
    print("Iterative Fibonacci Sequence: " ,
        [iterative_fib(i) for i in range(nterms)])

我如何使用此Fibonacci的迭代函数？

How would I use an iterative function with this Fibonacci?

我试过这个：

def iterative_fib(n):
    equation = lambda n: int((((1 / (5 ** 0.5)) * (1 + (5 ** 0.5))) ** n) - (((1 / (5 ** 0.5)) * (1 - (5 ** 0.5))) ** n))
    if n <= 1:
        return equation(n)
    else:
        a, b = 1, 2
        for i in range(n):
            fn = equation((i-a)+(i-b))
        return fn

然而，这个迭代函数似乎没有与递归函数相同的输出。

However this iterative function doesn't seem to have the same output as the recursive function.

递归函数的输出：

Recursive Fibonacci Sequence:  [0, 2, 2, 4, 6, 10, 16, 26, 42, 68]

输出迭代函数：

Iterative Fibonacci Sequence:  [0, 2, 2, 2, 3, 6, 13, 27, 58, 122]

推荐答案

等式你我试着去做plement是封闭形式 Fibonacci系列。

The equation you're trying to implement is the closed form Fibonacci series.

封闭形式意味着评估是一个恒定的时间操作。

Closed form means that evaluation is a constant time operation.

g = (1 + 5**.5) / 2  # Golden ratio.
def fib(N):
    return int((g**N - (1-g)**N) / 5**.5)

对比，

def fib_iterative(N):
    a, b, i = 0, 1, 2
    yield from (a, b)
    while i < N:
        a, b = b, a + b 
        yield b
        i += 1

我们有

>>> [fib(n) for n in range(10)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
>>> list(fib_iterative(10))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

这篇关于封闭形式斐波那契系列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！