斐波那契数列(python)
def fib(n):"""计算第n项的值"""if n <= 2:return n -1return fib(n-1) + fib(n-2)print(fib(10))#第10项斐波那契数列print("-"*30)sum =0for i in range(1,10):#前10项斐波那契数列之和sum += fib(...
·
def fib(n):
"""
计算第n项的值
"""
if n <= 2:
return n -1
return fib(n-1) + fib(n-2)
print(fib(10)) #第10项斐波那契数列
print("-"*30)
sum =0
for i in range(1,10): #前10项斐波那契数列之和
sum += fib(i)
print(sum)
def fib_n(n):
"""
#计算前n项斐波那契数列之和的函数
"""
a = [0,1]
if n <= 2:
return a[:n] #取到0,1在n = 1 和 n = 2
for i in range(n-2): #前面的两项已经计算了所以用n-2
c = a[-1] + a[-2]
a.append(c)
return a
n = 10
print(fib_n(n))
为什么要用fib_n 函数,因为用循环去计算,它还会重新计算一遍,这会计算时间过长。使用fib_n函数会减少计算量。
接着补充新的计算方法。因为计算很大的fib函数比如第100,这样我们上面的方法会比较慢。所以我们思考,既然fib(n) = fib(n-1) + fib(n-2)。这样我们会无形的计算很多次重复的计算我们可以引入一个memo记录我们已经计算过的数相当于记事本,我们可以快速得到,不用重复计算从而缩短时间。
def fib(n , memo = {}):
"""
带记事本的计算方法
"""
if n in memo:
return memo[n] #判断在memo中直接使用该值
elif n == 0:
return 0
elif n == 1:
return 1
else:
ans = fib(n-1) + fib(n-2)
memo[n] = ans
return ans
print(fib(100,{}))
今天又新学到了一种方法计算fib(n),感觉特别的简单。在这里不好说明,就在代码了呈现。
def fib(n):
a = 0
b = 1
for i in range(n):
a, b = b, a+b
# 循环的过程中根据fib(n) = fib(n-1) + fib(n-2)。a相当于fib(n-2) b相当于fib(n-2)这样我们可以计算出我们想要的值
return a
print(fib(100))
更多推荐
所有评论(0)