Java教程

算法第二章上机实践报告

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

算法第二章上机实践报告

一、实践题目名称

二分法求函数的零点

二、问题描述

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

求出给定函数的根,该根结果与函数真实结果相差不超过0.0000001

三、算法描述

1、定义:定义并输入变量l、r 、mid,一个布尔函数用于判断该根结果是否与真实结果相差超过0.0000001

2、初始化:double l=1.5, r=2.4, mid=(l+r)/2, bool check( )

3、运用分治法

分:先将题目划定区间一分为二,中间值为mid;

治:对划定的mid值进行求解判断结果是否符合;

最终输出可行的结果。

不断缩小结果的可能范围,达到精确范围

递归式为:

mid=(l+r)/2

if(check(mid))l=mid

else r=mid

代码如下:

}

四、算法时间及空间复杂度分析

此算法实现的时间复杂度和空间复杂度都为 log2n级别的。

时间复杂度O(log2n):查找长度为n,每次查找后长度减半,T(n)=2T(n/2)

空间复杂度O(log2n)。

五、心得体会
1、学会绘图辅助思考,算法不能凭空想象,有时绘图,给出具体的数据更加有助于求解

2、要多方面思考问题,函数有递增递减,两种都要思考,看清题目限制了为递减

3、对于无线接近有正向接近还有反向接近,因此接近值要加绝对值

六、分治法的个人体会和思考

1、分治法可以将一个庞大的问题细分,更加有助于问题的解决

2、分治法很重要的是如何划分问题,子问题越多有时会加大问题的复杂性

3、分治法处理得当可以大大降低问题的时间和空间复杂性

 

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