Python 求斐波那契数列前20项和

Python 求斐波那契数列前20项和

定义：斐波那契数列（Fibonacci sequence），又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）


方法一：用递归方法求出每一项
def fib1(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib1(n - 1) + fib1(n - 2)
res = []
for i in range(21):
    res.append(fib1(i))
print res
print sum(res)

方法二：上面的方法，有很多重复计算，非常消耗性能，下面改进下：

known = {0: 0, 1: 1}
def fib2(n):
    if n in known:
        return known[n]
 
    res = fib2(n - 1) + fib2(n - 2)
    known[n] = res
    return res
res = []
for i in range(21):
    res.append(fib2(i))
print res
print sum(res)追问我要求前20项和追答最后的sum(res)就是求和。你自己跑下看看。你将range(21)改成range(20)。