定义一个函数:斐波那契数列

Question

定义一个函数来实现斐波那契数列：1、1、2、3、5、8、13、21、34。请使用函数输出斐波那契数列的前 20 位数字。

Answer 1

这是一个python实现

def fib(n):
a, b = 0, 1
while a < n:
print(a, end=' ')
a, b = b, a+b
print()
fib(5000)

输出

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

递归实现

memo = [-1] * 21
memo[0] = 0
memo[1] = 1
print(memo[0], end=' ')
print(memo[1], end=' ')
def fibrec(n):
if(memo[n] == -1):
memo[n] = fibrec(n-2) + fibrec(n-1)
print(memo[n], end=' ')
return memo[n]
fibrec(20)

输出

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765