算法第2章实践报告

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

题目：7-2 二分法求函数的零点 

1、问题描述

有函数：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

2、算法描述

算法：二分法

已知x=1.5时，f(x)>0,x=2.4时，f(x)<0，求解的x在[1.5,2.4]的范围之间

f（x）在定义域[1.5,2.4]中是单调递减，因此，有如下判断：

• 当f(x)>0时，将中值mid赋给右端的r赋给左端的l
• 当f(x)<0时，将中值mid赋给左端的l赋给右端的r

运用二分法，不断缩小x的定义域

当f(mid)=0时，停止递归

输出最后结果

ps：浮点型不可能完全等于零。所以为了判读，需要加上一个范围1e-7。当在0附近1e-7范围内都当作等于0

ps：fabs（x）为对x求绝对值

3、时间复杂度分析

最好情况：

出现在第一次的mid就是答案，所用时间是O(1)

一般情况：

总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k .....其中，k是循环的次数
由于n/2^k取整后>=1，即令n/2^k=1
得k=log2n,（是以2为底数，n为对数）

故时间复杂度为O(logn)

4、空间复杂度分析

本题只用mid辅助查找，不需要额外的存储空间，因此空间复杂度为O(1)。

5、求解思想：

这一道题是运用了二分法的思想进行求解。

二分法使用过程中，要根据mid与要求的x之间的关系，以及f（x）从左到右单调递减的性质，从而返回不一样的值，从而逐渐得到最终结果。

6、心得感悟：

1、分治法：将大规模的问题分解为若干个子问题，由大化小来提高解决问题的效率。通常是采用递归法来求解子问题，子问题规模小到一定程度，种植递归，求解答案。原问题的解是子问题的答案的合并。

2、注意的点：解题时要弄清楚大于、小于要返回什么值，这里很容易出错弄反。

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