算法第二章上机实践报告

1. 实践题目名称

二分法求函数的零点

2. 问题描述

有函数：f(x)=x^5 - 15x^4 + 85x^3 - 225x^2 + 274x - 121， 已知f(1.5)>0,f(2.4)<0 且方程f(x)=0 在区间[1.5,2.4] 有且只有一个根，请用二分法求出该方程在区间[1.5,2.4]中的根并输出。要求四舍五入到小数点后6位。 提示：判断函数是否为0，使用表达式 fabs(f(x)) < 1e-7

3. 算法描述

使用二分法，由题可知，这个函数在[1.5,2.4]内单调递减，当f(x)>0时，将mid+1赋给左边界left；当f(x)<0时将mid-1赋给右边界right。通过不断地取left，right的中值，进行查找比较，当right，left之间的距离小于1e-7时停止，此时的f(mid)为0或非常接近0，mid则为所求的根。

void bSearch(double left, double right) {
	if (fabs(right - left) > 1e-7) {
		mid = (left + right) / 2;
		if (f(mid) > 0)
		    return bSearch(mid+1, right);
		if (f(mid) < 0)
		    return bSearch(left, mid-1);
	}
}

4.算法时间即空间复杂度分析

时间复杂度：采用分治策略，分解子问题的时间复杂度为O(1)，每个子问题的规模为n/2，则解决子问题所需时间为T(n/2)，所以T(n)=O(1)+T(n/2)=O(logn)

空间复杂度：该算法用了递归，每次递归中需要的空间是一个常量，并不会随着n的变化而变化，每次递归的空间复杂度就是O(1)。又递归深度为logn，所以该算法的空间复杂度为O(1*logn)=O(logn)

5. 心得体会

从这次的实践中，我明白了在打代码前一定要读懂题目，灵活运用题目给的条件和提示，而不是不经思考就将题目给出的打出来，有时候这样会固定思维，如果代码不符合要求，就不容易找到错误的点在哪。此次实践的方式为两人一组，一人打代码，另一人看，我也充分意识到了代码规范整洁尤为重要。

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

分治法的基本思想主要分为三步：整个问题划分为多个子问题、求解各子问题、合并子问题的解。分治法所能解决的问题一般其规模缩小到一定的程度就可以容易地解决，该问题分解出的子问题的解可以合并为该问题的解。可使用分治法求解的一些经典问题有：二分搜索、大整数乘法、Strassen矩阵乘法、棋盘覆盖、合并排序、快速排序、线性时间选择、最接近点对问题、循环赛日程表、汉诺塔等。