(python编程)使用函数输出斐波那契数列：[-1, -1, -2, -3, -5, -8, -13, -21, -34, -55]（添加到列表）？
发布网友
发布时间：2022-04-06 07:26
共2个回答
懂视网
时间：2022-04-06 11:47
对于学习编程语言的小伙伴们来说，斐波那契数列将是一个最经典的函数之一，今天用Python来给大家讲讲这个经典的函数怎么简单粗暴的实现。
实现之前呢，先给大家介绍一下斐波那契数列的原理，原题是一个兔子繁殖问题，简单的讲就是后一项等于前两项之和，即f(x)=f(x-1)+f(x-2)，第一项可为0，亦可为1。
下面介绍两种常用的方式，或许没别人写的那么简洁，请见谅哈！
第一种：非递归方式，用的是索引和while循环相结合
# 从零开始，输出前n项斐波那契数列
# 定义斐波那契函数
def fibo(x):
#初始化前两项
m=0
n=1
# 用list存储
l=[0,1]
# 设定初始项
i=2
# 用while循环进行运算,原理：后一项等于前两项之和
while i<x:
# m+n赋值给n
n=m+n
# 将n添加至list
l.append(n)
# 通过索引将list的前一项赋值给m
m =l[i-1]
#通过自加来达到退出循环的条件
i=i+1
#打印出list
print(l)
# 调用函数
fibo(10)
第二种：递归方式实现，这种就是经典模型了
# 从零开始，输出第n项斐波那契数列
def fibo(x):
if x==1:
return 0
elif x==2:
return 1
elif x>2:
return fibo(x-1)+fibo(x-2)
else:
print("输入错误，请重新输入！")推荐教程： 《Python教程》
热心网友
时间：2022-04-06 08:55
你看看你递归代码的复杂度 是O(2^n) 而第二个的复杂度是O(n) 运行效率当然不同COUNTER = 0
def fibn(n):
global COUNTER
COUNTER += 1
if n == 0:
return 1
elif n == 1:
return 1
else:
return fibn(n-1) + fibn(n-2)
statistics = []
for i in range(35):
COUNTER = 0
fibn(i + 1)
statistics.append(((i + 1), COUNTER))
print statistics[(1, 1), (2, 3), (3, 5), (4, 9), (5, 15), (6, 25), (7, 41), (8, 67), (9, 109), (10, 177), (11, 287), (12, 465), (13, 753), (14, 1219), (15, 1973), (16, 3193), (17, 5167), (18, 8361), (19, 13529), (20, 211), (21, 35421), (22, 57313), (23, 92735), (24, 150049), (25, 242785), (26, 392835), (27, 635621), (28, 1028457), (29, 16079), (30, 2692537), (31, 4356617), (32, 7049155), (33, 11405773), (34, 18454929), (35, 29860703)]做了一个简单的proflieimport cProfile
import pstats
def fibn(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return fibn(n-1) + fibn(n-2)
print ' i, calls, time'
for i in range(50):
pr = cProfile.Profile()
pr.enable()
fibn(i)
pr.disable()
stats = pstats.Stats(pr)
stats.strip_dirs()
st = stats.stats[('test1.py', 3, 'fibn')]
print '%3d, %10d, %8f' % (i, st[1], st[3])
i, calls, time 0, 1, 0.000000 1, 1, 0.000001 2, 3, 0.000003 3, 5, 0.000005 4, 9, 0.000008 5, 15, 0.000012 6, 25, 0.000020 7, 41, 0.000033 8, 67, 0.000165 9, 109, 0.000088 10, 177, 0.000141 11, 287, 0.000228 12, 465, 0.000450 13, 753, 0.000601 14, 1219, 0.001016 15, 1973, 0.003561 16, 3193, 0.002593 17, 5167, 0.004372 18, 8361, 0.007097 19, 13529, 0.011073 20, 211, 0.018552 21, 35421, 0.032467 22, 57313, 0.051762 23, 92735, 0.095383 24, 150049, 0.133490 25, 242785, 0.212390 26, 392835, 0.352861 27, 635621, 0.578204 28, 1028457, 0.987839 29, 16079, 1.506812 30, 2692537, 2.682802 31, 4356617, 3.9936 32, 7049155, 8.0419 33, 11405773, 13.058235 34, 18454929, 23.930004 35, 29860703, 36.503880目测fibn(50)要算出来需要两周
