算法第二章上机实验报告

本文主要是介绍算法第二章上机实验报告，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1实践题目名称：

二分法求函数的零点

2问题描述：

有函数：f(x)=x5-15*x4+85*x3-225*x2+274*x-121 已知f(1.5)>0，f(2.4)<0且方程f(x)=0在区间【1.5, 2.4】有且只有一个根，请用二分法求出该根。提示：判断函数是否为0，使用表达式fabs(f(x))<1e-7

3算法描述：

根据分治法的思想，不断缩小【1.5, 2.4】，不断取区间中点判断是否为方程的根。根据二次函数的图像以及区间中点的函数值正负来判断区间往哪个方向缩小：若区间中点函数值大于零，往右边缩小；若区间中点函数值小于零则往左边缩小。由于题目中要求方程的根保留小数点后六位，故终止缩小区间的循环条件是区间长度小于1e-7.

4算法时间及空间复杂度分析：

时间复杂度：根据二分法的思想，每次查找的区间长度为n, n/2, n/4……最后区间长度为1，所以时间复杂度为logn

空间复杂度：因为循环没有额外开启别的数据空间，故空间复杂度为1

5心得体会：

一开始不是很明白表达式fabs(f(x))<1e-7的意思，后来才知道由于浮点数的精度较差，所以区间长度小于1e-7时认为此时中点是方程的根，所以终止缩小区间的循环条件是区间长度小于1e-7。利用分治法解决问题时，要注意left，mid和right之间的关系。

6分治法的个人体会和思考：

分治法是一种很重要的算法，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单地直接求解，元问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法，傅里叶变换等。

这篇关于算法第二章上机实验报告的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！