Java教程

算法第二章上级实验报告

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

实践题目名称:

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

 

问题描述:

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

 

算法描述:

//分治法,利用递归的方法

double biSearch(double start, double end){

       double mid = (start + end)/2.0;

//中点值近似于0,则直接返回中点

       if(fabs(f(mid)) < 1e-7)

              return mid;

//中点值大于0,则查找右半部分区间,向右递归

       else if(f(mid) > 0)

              return biSearch(mid,end);

//中点值小于0,则查找左半部分区间,向左递归

       else

              return biSearch(start,mid);

}

 

算法时间及空间复杂度分析:

时间复杂度为O(1),题中直接给出常数范围区间[1.5,2.4];

空间复杂度为O(1),题中无输入数组;

 

心得体会:

本次上机实验课,让我对分治法有了更多的了解和使用,将问题规模缩小到一定的程度进行就会更容易解决,两人一组做题过程中也会出现疑点,第一题递归的区间范围选择,然后第二题的一点bug,很多细节上的漏洞都是需要两人合作去找出,并且互相对代码的讲解,能从中收获更多。

 

分治法的个人体会和思考:

分治法的三步骤,问题分解、求解子问题、合并子解,分治法的设计思想就是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。所以当问题规模很大时,适当地采取这种方法是更能提高时间效率的,在实验完成后我们也要对能使用分治法的题型有所了解,做到举一反三,这对提高我们的编码质量有很大的帮助。

 

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