实验6-CS1806-U201814788-刘美1
需积分: 0 31 浏览量
2022-08-08
19:38:39
上传
评论
收藏 60KB DOCX 举报
实验六：斐波那契(Fibonacci)数列计算器设计
1. 给出 Fibonacci 数列通项公式、Fibonacci 数列的递归算法（指数时间复杂度）
形式化描述、Fibonacci 数列的多项式时间复杂度算法形式化描述；
数列通项公式：
FFF
nnn )2()1()( ��
��
递归算法的形式化描述：
图 6-1 递归算法形式话描述
时 间 复 杂 度 为 ： 求 解 通 项 公 式 得 到 时 间 复 杂 度 为
])
2
51
()
2
51
[(
5
1
x
nn
�
�
�
�
，即 O（2^n）
数列多项式伪代码：
初始化：
X
=
A
=
0
1
1
1
, Start=0；
For (i=5 downto 0)
评论0