实验二:递归与递推
1. 实验目的
以斐波那契数列为例,掌握递归与递推算法。
2. 实验内容
斐波那契数列
请用三种方式写出求斐波那契数列第n项,包括普通递归,带缓存数组的递归以及递推法。斐波那契数列的公式如下:
f(n)={1f(n−1)+f(n−2)if n=1,2if n>2
输入样例
第一行n,表示求斐波那契数列的第n项
5
输出样例
包含一个数字,为斐波那契数列的第n项。
5
算法分析
针对斐波那契数列的算法,请进行以下分析:
- 选取不同的n,用表格的形式测试对于不同的n,算法的运行时间。(注意n的选取)
- 分析算法间效率的差距
- 对于不带缓存数组的递归形式,请画出n=5时的递归树
3. 实验要求
请写出题目的思路、代码,并完成算法分析。
提示:
- linux下可以使用time命令测量程序运行时间
- 在语言中可以使用语言自带的时间函数,作差进行时间测量