斐波那契数列计算器 python

Question

您好，我是 python 的新手，我正在尝试创建一个斐波那契计算器函数来打印给定数字以内的所有值，如果输入的数字不在序列中，那么它会添加下一个斐波那契列表中的编号。例如，如果输入 10，则应 return [0, 1, 1, 2, 3, 5, 8, 13]。该函数必须是递归的。这是我当前的代码：

def fibonacci(n):
    n = int(n)
    # The nested sub_fib function computes the Fibonacci sequence

    def sub_fib(n):
        if n < 2:
            return n
        else:
            return (sub_fib(n-1) + sub_fib(n-2))

    #This aspect of the main fib function applies the condition if the number
    # input is not in the sequence then it returns the next value up

    fib_seq= [sub_fib(i) for i in range(0,n) if sub_fib(i)<=n]
    if fib_seq[-1] < n:
        fib_seq.append(fib_seq[-1] + fib_seq[-2])
        return fib_seq
    else:
        return fib_seq
print(fibonacci(input("Input a number to print sequence up to: ")))

我已经设法让它工作了，但是它非常慢（我假设是由于递归）我是否可以在不大量更改程序的情况下加快它的速度？

Answer 1

你的程序运行缓慢的两个主要原因：

您单独计算每个斐波那契数，您没有重复使用您为寻找前一个数所付出的努力；
你计算了第一个 n 斐波那契数列，但是从 条件失败的那一刻起，你可以停止 .

您可以将程序更改为仍然是递归的，但是重新使用计算前一个数字的工作，并在构建列表的那一刻停止。

您只需使用以下功能：

def fibon(a,b,n,result):
    c = a+b
    result.append(c)
    if c < n:
        fibon(b,c,n,result)
    return result

我们用 fibon(0,1,n,[]) 初始化它。在每次迭代中，它将计算下一个斐波那契数 c = a+b 并将其附加到 result。如果该数字仍然小于 c < n 那么我们需要计算下一个数字，从而执行递归调用。

def fibonacci(n):
    n = int(n)

    def fibon(a,b,n,result):
        c = a+b
        result.append(c)
        if c < n:
            fibon(b,c,n,result)
        return result

    return fibon(0,1,n,[])

print(fibonacci(input("Input a number to print sequence up to: ")))

Answer 2

这使用递归，但比简单的递归实现快得多

def fib(n):
    if n == 1:
        return [1]
    elif n == 2:
        return [1, 1]
    else:
        sub = fib(n - 1)
        return sub + [sub[-1] + sub[-2]]

Answer 3

以下是一些可以提高速度的示例：

"""
Performance calculation for recursion, memoization, tabulation and generator

fib took: 27.052446
mem_fib took: 0.000134
tabular_fib took: 0.000175
yield_fib took: 0.000033
"""
from timeit import timeit


LOOKUP_SIZE = 100
number = 30
lookup = [None] * LOOKUP_SIZE


def fib(n):
    return 1 if n <= 2 else fib(n - 1) + fib(n - 2)


def mem_fib(n):
    """Using memoization."""
    if n <= 2:
        return 1
    if lookup[n] is None:
        lookup[n] = mem_fib(n - 1) + mem_fib(n - 2)

    return lookup[n]


def tabular_fib(n):
    """Using Tabulation."""
    results = [1, 1]
    for i in range(2, n):
        results.append(results[i - 1] + results[i - 2])
    return results[-1]


def yield_fib(n):
    """Using generator."""
    a = b = 1
    yield a
    yield b
    while n > 2:
        n -= 1
        a, b = b, a + b
        yield b


for f in [fib, mem_fib, tabular_fib, yield_fib]:
    t = timeit(stmt=f"f({number})", number=10, globals=globals())
    print(f"{f.__name__} took: {t:.6f}")

斐波那契数列计算器 python

Fibonacci sequence calculator python

python

recursion

performance

fibonacci