使用O(1)空间在Python中自底向上斐波那契 [英] bottom up fibonacci in python using O(1) space

问题描述

我想使用O(1)空间写一个自下而上的斐波那契.我的问题是python的递归堆栈限制了我测试大量数字的能力.有人可以提供我所拥有的替代产品或优化产品吗?这是我的代码:

def fib_in_place(n):
    def fibo(f2, f1, i):
        if i < 1:
            return f2
        else:
            return fibo(f1, f2+f1, i -1)
    return fibo(0, 1, n)

解决方案

您可以记住Fibonacci函数的效率，但是如果您需要递归函数，则它至少仍需要O(n):

def mem_fib(n, _cache={}):
    '''efficiently memoized recursive function, returns a Fibonacci number'''
    if n in _cache:
        return _cache[n]
    elif n > 1:
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

这来自我对Python中主要斐波那契问题的回答:如何用Python编写斐波那契序列

如果允许使用迭代而不是递归，则应执行以下操作:

def fib():
    a, b = 0, 1
    while True:            # First iteration:
        yield a            # yield 0 to start with and then
        a, b = b, a + b    # a will now be 1, and b will also be 1, (0 + 1)

用法:

>>> list(zip(range(10), fib()))
[(0, 0), (1, 1), (2, 1), (3, 2), (4, 3), (5, 5), (6, 8), (7, 13), (8, 21), (9, 34)]

如果您只想获取第n个数字:

def get_fib(n):
    fib_gen = fib()
    for _ in range(n):
        next(fib_gen)
    return next(fib_gen)

和用法

>>> get_fib(10)
55

I want to write a bottom up fibonacci using O(1) space. My problem is python's recursion stack is limiting me from testing large numbers. Could someone provide an alternate or optimization to what I have? This is my code:

def fib_in_place(n):
    def fibo(f2, f1, i):
        if i < 1:
            return f2
        else:
            return fibo(f1, f2+f1, i -1)
    return fibo(0, 1, n)

解决方案

You can memoize the Fibonacci function for efficiency, but if you require a recursive function, it's still going to take at least O(n):

def mem_fib(n, _cache={}):
    '''efficiently memoized recursive function, returns a Fibonacci number'''
    if n in _cache:
        return _cache[n]
    elif n > 1:
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

This is from my answer on the main Fibonacci in Python question: How to write the Fibonacci Sequence in Python

If you're allowed to use iteration instead of recursion, you should do this:

def fib():
    a, b = 0, 1
    while True:            # First iteration:
        yield a            # yield 0 to start with and then
        a, b = b, a + b    # a will now be 1, and b will also be 1, (0 + 1)

usage:

>>> list(zip(range(10), fib()))
[(0, 0), (1, 1), (2, 1), (3, 2), (4, 3), (5, 5), (6, 8), (7, 13), (8, 21), (9, 34)]

If you just want to get the nth number:

def get_fib(n):
    fib_gen = fib()
    for _ in range(n):
        next(fib_gen)
    return next(fib_gen)

and usage

>>> get_fib(10)
55

这篇关于使用O(1)空间在Python中自底向上斐波那契的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！