个人做的课后练习

书籍：算法设计与分析基础(第三版）

习题2.5

二. 一直按每一个月写出兔子对数： 2 3 5 8 13 21 34 55 89 144 233 377

三.假设n格有F（n）种爬法，有递推公式： F（n）=F（n-1）+F（n-2）

四. n/3 向下取整

五. 代入即可立即得到答案。

六. a. n为48时，会溢出 b. n为94时，会溢出

八.

Fibonacci(n) a←1 b←0 while(n>0) do b←b+a a←b-a n-- return b;

九. 直接使用数学归纳既可以证明。

十. n次

十一. 如果选择输入大的数字为输入规模。 时间复杂度为 O（log(n)）

十二. a.

Fibonacci(n) if n==0 or n==1 return n; else return （Fibonacci(n-1)+Fibonacci(n-2))0000

b.

Fibonacci(n) a←1 b←0 while n>0 do b←b+a a←b-a b←b%100000 n-- return b