根据斐波那契数列的定义 F（0)=0 F（1)=1 F（n)=F（n–1)+F（n–2)（n≥2) 输出不大于100的序列元素 提示
已帮助 人
根据斐波那契数列的定义，F（0)=0，F（1)=1, F（n)=F（n–1)+F（n–2)（n≥2)，输出不大于100的序列元素，提示代码如下： a,b = 0, 1 while a<100: print（a,end=",") a,b=______________
回答
共1条回复-
(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=012…n-1)由以上等式可知F n-1 被执行一次即B n-1 =1；F n-2 被执行再次即B n-2 =2；直至F 1 被执行p次F 0 被执行q次即B 0 =pB 0 =q。B m 的执行次数为前两等式第一因式系数之和即B m =B m-1 +B m-2 再有B n-1 =1和B n-2 =2这也是一个斐波那契数列。可以解得： (2)时间复杂度为O(n)。 本题主要考查递归算法的时间复杂度。考生应该比较熟悉斐波那契数列，只要具备一定的数学功底，解决该题应该没有什么困难。但是，通过该题需要掌握将实际问题转换成数据结构，进而能够通过数学分析得到时间复杂度的能力。