计软实验三：分治算法1
需积分: 0 150 浏览量
2022-08-04
15:32:04
上传
评论
收藏 355KB PDF 举报
《计算机软件基础》实验指导书
1
计软实验三：分治算法
一、 实验目的
通过编程熟悉并掌握分治算法，了解最大子数组问题和矩阵相乘的算法。
二、 实验内容
求连续子数组的最大和
1. 给 定 一 个 整 数 数 组
以及它的长度 。
2. 通过遍历所有子数组以及分治算法分别求解连续子数组的最大和，并返回这个数组
起始点和终点的位置。
3. 比较通过遍历求解和分治算法求解在时间上的差别。
4. 在之前的基础上，随机生成长度分别为，的数组，数组中的每个元素
为区间 的随机整数，分别用遍历算法和分治算法求解最大子数组，并比
较它们在时间上的差别。
三、 实验步骤
1. 设
，从 处将原数组分成两个数组，先在两个数组中分别搜索最大子数组，
再在跨越分界线的数组中寻找最大子数组。
：左半个数组的最大子数组。
：右半个数组的最大子数组。
：以分界线为终点的最大子数组。
：以 为起点的最大子数组。
2. 整个数组的最大子数组一定是在
，
和（跨越分界线的最大子数组）这三
种情况中选取和的最大值，其中一定为
与
的和。
3. 上述划分过程还可继续进行，直到不可再分。
评论0