更新时间:2023-08-27 18:13:10
您可以编写一个fibonacci函数,该函数以线性时间运行并且具有恒定的内存占用,因此不需要列表即可保留它们. 这是一个递归版本(但是,如果n足够大,它将只是 *** )
You can write a fibonacci function that runs in linear time and with constant memory footprint, you don't need a list to keep them. Here's a recursive version (however, if n is big enough, it will just ***)
def fib(a, b, n):
if n == 1:
return a
else:
return fib(a+b, a, n-1)
print fib(1, 0, 10) # prints 55
此函数仅调用一次(导致大约N调用参数N),而您的解决方案则调用两次(大约2 ^ N调用参数N).
This function calls itself only once (resulting in around N calls for a parameter N), in contrast with your solution which calls itself twice (around 2^N calls for a parameter N).
这是一个永远不会堆栈溢出的版本,它使用循环而不是递归:
Here's a version that won't ever *** and uses a loop instead of recursion:
def fib(n):
a = 1
b = 0
while n > 1:
a, b = a+b, a
n = n - 1
return a
print fib(100000)
那已经足够快了:
$ time python fibo.py
3364476487643178326662161200510754331030214846068006390656476...
real 0m0.869s
但是调用fib
直到获得足够大的结果并不完美:意甲联赛的第一个数字被多次计算.
您可以计算下一个斐波那契数,并在同一循环中检查其大小:
But calling fib
until you get a result big enough isn't perfect: the first numbers of the serie are calculated multiple times.
You can calculate the next fibonacci number and check its size in the same loop:
a = 1
b = 0
n = 1
while len(str(a)) != 1000:
a, b = a+b, a
n = n + 1
print "%d has 1000 digits, n = %d" % (a, n)