使用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屋!