实 验 报 告
一、实验目的
1、理解递归算法的思想和递归程序的执行过程,并能熟练编写递归程序。
2、掌握分治算法的思想,对给定的问题能设计出分治算法予以解决。
二、实验内容
1、对求解最大子段和问题用 C/C++以及 JavaScript 语言编写程序并调试演示。
2、对算法进行优化和分析,撰写不少于 2000 字的小论文。
三、实验环境
Windows/mac OS Dev-C++ 5.11 Visual Studio Code 1.45.0
四、问题分析
(1)采用分治法求解,最大子段和的位置有可能出现在哪里?
(2)算法时间复杂度、空间复杂度分析
1、for 循环的时间复杂度为 n
2、分治法存在递推公式
3、因为可以看成一棵二叉树,因此借用堆栈的思想,它的空间复杂度可能为 O(n)
五、问题解决
1、采用分治法求解,获取数组中心点,最大子序列有三种情况
1、在中点左边 2、在中点右边 3、跨中点
课程名称:算法设计与分析
班级:计算机 1801 班
实验成绩:
实验名称:分治策略
学号:1820100
批阅教师签字:
实验编号:实验一
姓名:吕志鹏
实验日期: 2020 年 5 月 12
日