算法第二章上机实践报告
2021/10/3 22:10:49
本文主要是介绍算法第二章上机实践报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
算法第二章上机实践报告
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矩阵乘法、棋盘覆盖、合并排序、快速排序、线性时间选择、最接近点对问题、循环赛日程表、汉诺塔等。
这篇关于算法第二章上机实践报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-29P标签教程:初学者必备指南
- 2024-09-29PS网页切图教程:新手必学的网页设计技巧
- 2024-09-29简单易懂的Web布局教程
- 2024-09-29Web网页开发教程:从零开始的简单入门指南
- 2024-09-298D项目实战:新手入门教程
- 2024-09-29变形项目实战:新手必备入门指南
- 2024-09-29弹性盒子布局项目实战:从入门到上手
- 2024-09-29点击加载项目实战:新手入门必读教程
- 2024-09-29电商网页开发项目实战:新手入门教程
- 2024-09-29封装项目实战:从入门到初级应用