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

输出格式:该方程在区间[1.5,2.4]中的根。要求四舍五入到小数点后6位。

 

三、编写的代码

#include <iostream>
#include <iomanip>
#include <math.h>
using namespace std;
double f;
int flag;
double bsort(double l, double r)
{
    while (r-l >= 1e-6)
    {
        double mid = (l + r) / 2;
        f = pow(mid, 5) - 15 * pow(mid, 4) + 85 * pow(mid, 3) - 225 * pow(mid, 2) + 274 * mid - 121;
        if (f == 0)
        {
            flag = 1;//找到根,将flag置为1
            return mid;
        }
        if (f > 0)
        {
            l = mid;
        }
        else if (f < 0)
        {
            r = mid;
        }
    }
    if (!flag)//不断二分后仍未找到根
        return r;
}

int main() {
    double x = bsort(1.5, 2.4);
    cout << fixed << setprecision(6) << x;
    return 0;
}

 

四、算法描述

 

 已知 f(1.5) > 0, f(2.4) < 0,可绘出函数大致图像如图,在区间(1.5, 2.4)内必有一根。我们采用二分法的思想去分割区间,逼近这个根。

 

 

 首先,设区间的左起点l为1.5,右起点r为2.4,令mid=(l+r)/2,这样我们就得到了区间的中点mid,如图,若 f(mid)>0,那么说明根还在原区间的右半部分,所以我们以mid作为新区间的左起点l,右起点仍为r,再对新区间进行二分分割。

 

 

 如图,若 f(mid)<0,那么说明根在原区间的左半部分,所以我们以mid作为新区间的右起点r,左起点仍为l,再对新区间进行二分分割。

 

 

 mid=(l+r)/2,得到的新中点,如果f(mid)大于0、f(r)<0的话,那么就说明根在右半部分,我们重复上述步骤,将mid作为新区间的左起点l,右起点仍为r,再对新区间进行二分分割。

重复以上步骤,不断分割区间,区间的范围不断缩小为原先的1/2、1/4、1/8……如果区间足够小时,比如说区间的长度已经小于0.000001,也就是已经到了小数点后六位,根据题目的要求(该方程在区间[1.5,2.4]中的根,要求四舍五入到小数点后6位),我们可以认为在这个区间内的所有数值,都是这个方程的根,那么就可以结束分割了。

 

五、算法时间复杂度分析

这道题可以看成是在长度为N的区间内寻找唯一的零点,第一次分割区间后查找分为变成了N/2,第二次分割后范围变成了N/4,第n次分割后查找范围就是N/(2)^n,直到最后查找范围(区间长度)为1,也就是找到了那个数。二分的次数就是基本语句执行的次数,设一共执行了n次分割,可得:

 

 N也就是我们所说的问题规模。

 

六、时间复杂度分析

本题无需额外的存储空间,故空间复杂度为O(1)。

 

七、心得体会

这次实验是两个人合作一起完成的,比起以前写代码时都是一个人写,两个人一起合作的时候,编写者(我)难免会犯一些没有察觉到的错误,我的同伴都马上指出了。这次实验我还没有做到解题完全独立,这三道题几乎都是两个人一起一边讨论一边写、一边改出来的。希望我以后能多加强这方面的锻炼和学习。

 

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

我觉得分治法的思想是一个非常好的思想,将问题细分成和原问题一样的小问题(分),再解决小问题(治),最终合并小问题的解,就得到了原问题的解(合)。有时候一些很复杂的问题,例如汉诺塔问题,乍一看情况很多变,无从下手,但运用分治法的思想后,可以将原问题细化成一目了然的小问题,这些小问题一下子就能找到解决方案,最终也解决了棘手的大问题。

分治法中运用的递归方法我还很不熟练,很多时候不知道什么时候要用递归、怎么用递归,希望日后多加强对递归的学习和运用。

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