求最大字段的三种方法—— 动态规划 蛮力 分治算法

}

}

end=clock();

usetime=end-start;

printf(\分治算法用时 %.f*10^(-6) 豪秒\\n\ usetime); start=clock(); i=1000000; while(i!=0) { dtgh(6,a); i--; }

end=clock();

usetime=end-start;

printf(\动规算法用时 %.f*10^(-6) 豪秒\\n\ usetime);

五、实验过程原始记录( 测试数据、图表、计算等)

请给出各个操作步骤的截图和说明； 实验结果截图如下：

测试数据为教材数据：a[6]={-20,11,-4,13,-5,-2};

-5-

从截图可以看出三种算法的结果都正确，代码成功。 第二组测试数据：：a[6]={ 20,11,-4,13,-5,-2};把-20改为20

实验数据再次说明代码成功：

六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）

实验结果：通过实验结果得到的结果可以看出实验成功，本次实验最难得算法是分治算法，但分治

算法的伪代码在教材上有，我通过教材的伪代码，我试着写了自己的代码。

实验分析：通过时间复杂度的分析，可以看出动态规划算法是最优的，其次是分治算法，最差的是蛮力算法，从计数得到的结果与预期的结果一致。但是本次试验出现的问题是在计时器里显示的数据分治算法的用时比蛮力算法的长，我认为造成这种结果的因素有两个：1、实验数据特殊，数据样本太小。2、因为蛮力算法程序只是一个两层循环，而分治算法的代码过长，导致我们的计时器得到的结果产生错误。

实验结论：本次实验成功得到结果，实验顺利完成。通过本次实验我进一步加深了算法的设计是多么的重要，一个好的算法意味着很多东西，不仅节约空间，最重要的是我们等待的时间。

请结合实验的结果分析算法原理；在实验中遇到了些什么问题，如何解决；有什么收获等；

注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。

-6-