首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
公务员
斐波那契数列Fn定义如下: F0=0, F1=1, Fn=Fn-1+Fn-2, n=2,3,… 请就此斐波那契数列回答下列问题: (1)在递归计算Fn时,需要对较小的Fn-1,Fn-2,…,F1,Fn精确计算多少次?
斐波那契数列Fn定义如下: F0=0, F1=1, Fn=Fn-1+Fn-2, n=2,3,… 请就此斐波那契数列回答下列问题: (1)在递归计算Fn时,需要对较小的Fn-1,Fn-2,…,F1,Fn精确计算多少次?
admin
2013-12-19
25
问题
斐波那契数列F
n
定义如下:
F
0
=0, F
1
=1, F
n
=F
n-1
+F
n-2
, n=2,3,…
请就此斐波那契数列回答下列问题:
(1)在递归计算F
n
时,需要对较小的F
n-1
,F
n-2
,…,F
1
,F
n
精确计算多少次?
(2)如果用大O表示法,试给出递归计算F
n
时,递归函数的时间复杂度为多少?
选项
答案
(1)由斐波那契数列的定义可得: F
n
=F
n-1
+F
n-2
=2F
n-2
+F
n-2
=3F
n-3
+2F
n-4
=5F
n-4
+3F
n-5
=8F
n-5
+5F
n-6
=pF
1
+qF
0
设Fm的执行次数为Bm(m=0,1,2,…,n-1),由以上等式可知,F
n-1
被执行一次,即B
n-1
=1;F
n-2
被执行再次,即B
n-2
=2;直至F
1
被执行p次,F
0
被执行q次,即B
0
=p,B
0
=q。B
m
的执行次数为前两等式第一因式系数之和,即B
m
=B
m-1
+B
m-2
,再有B
n-1
=1和B
n-2
=2,这也是一个斐波那契数列。可以解得:[*] (2)时间复杂度为O(n)。
解析
本题主要考查递归算法的时间复杂度。考生应该比较熟悉斐波那契数列,只要具备一定的数学功底,解决该题应该没有什么困难。但是,通过该题需要掌握将实际问题转换成数据结构,进而能够通过数学分析得到时间复杂度的能力。
转载请注明原文地址:https://kaotiyun.com/show/eSal777K
本试题收录于:
计算机专业知识题库事业单位考试分类
0
计算机专业知识
事业单位考试
相关试题推荐
设计课堂学习活动、布置课下作业时,教师需要注意的事项有()。
让儿童先去玩能体现数学概念的具体游戏,然后再接触完全符号化的概念。这是()。
某职业高中为了招揽生源,制定了一条潜规则,提出“对介绍和推荐学生实行奖励,只要新生报到注册,对该生的介绍人将付给一定的中介费”。某镇初中的班主任老师得知此消息后,将本班原打算读另一职高的三个学生动员到该职业高中就读,该职业高中立即履行了自己的承诺。对此行为
美国行为主义心理学家华生在《行为主义》一书中写道:“给我一打健康的婴儿,一个由我支配的特殊环境,让我在这个环境里养育他们,我可担保,任意选择一个,不论他父母的才干、倾向、爱好如何,他父母的职业及种族如何,我都可以按照我的意愿把他们训练成为任何一种人物——医
在教育统计分析中,标准差和全距属于()。
8岁的李林,尽管他的协调能力很差,但从表面看是一个喜欢运动、非常快乐的孩子,然而他干什么都是三分钟热度,上课总走神,学习成绩差,对于家长和老师的话充耳不闻,讨厌学习,在活动中表现霸道,几乎每天都被老师批评,许多孩子也不愿意和他一起玩。韦克斯勒儿童智力测试的
主管学校教育研究工作的陈校长上任伊始采取了三点策略:第一,鼓励教师多申报课题。第二,组织教师多参加培训。第三,要求教师多撰写论文。他为每个教师指定了公开课发表论文的数量,并定期检查结果。按照陈校长的策略,一年之内学校申报了十几项课题,开展了十几次讲座和报告
金明小时候总是生病,常影响功课,但学习成绩还不错。可是同学们都说他有传染病,这样一来,全班同学都躲着他。在这种气氛中,他形成了严重的厌学情绪,学习成绩也成了班上比较差的。厌学是由于人为因素所造成的儿童()上的失调状态。
编码系统和统觉团都属于个体的认知结构。()
structemployee{longnum;floatsalary;structemployee*next;};intn;struetemployee*del(struet
随机试题
以下电气设备中,属于防火重点设备的有()。
各种悬吊灯具离地面的距离不应小于()。
英国国家标准(),日本国家标准(),美国国家标准()。
通过把多项式分解因式,把函数f(x)=ln(1+X一2x2)展开为x的幂级数,并给出收敛域.
治疗小儿衣原体肺炎首选的抗生素是()。
房地产权属档案是权属管理活动中形成的历史记录,不但具有专业性、动态性、法律性,还具有()。
管线共沟敷设时,不符合规定的是()。
下列说法中对税务机关职权表述正确的是( )。
商业银行有效的战略风险管理应当确保其长期战略、短期目标、()和可利用资源紧密联系在一起。
天地悠悠悬秤杆,百姓芸芸秤砣心。严纲纪、正作风是一场大手术,唯有___________才能___________。填入画横线部分最恰当的一项是()。
最新回复
(
0
)