分治算法实验报告.docx_分治算法实验资源-CSDN文库

版权申诉

180 浏览量 2022-07-10 01:15:51 上传评论收藏 157KB DOCX 举报

资源推荐

资源详情

资源评论

算法分析与设计实验报告

第 1 次实验

姓名

时间

学号

地点

班级

10.17 上午

四合院 102

实验名称

分治算法实验（用分治法查找数组元素的最大值和最小值）。

通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。

在满足分治法的条件下，根据不同的输入用例，能准确的输出用例中的最

大值与最小值。并计算出程序运行所需要的时间。

分治法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问

题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子

问题的解合并得到原问题的解。

① 先解决小规模的问题，如数组中只有 1 个元素或者只有两个元素时候

的情况。

② 将问题分解，如果数组的元素大于等于 3 个，将数组分为两个小的数

组。

③ 递归的解各子问题，将(中分解的两个小的数组再进行以上两个步骤

((最后都化为小规模问题。

④ 将各子问题的解进行比较最终得到原问题的解。

void SelectMaxMin(int *a,int i,int j,int &max,int &min)

{

{

}

else

{

int mid=(i+j)/2;

int maxi,maxj,mini,minj;

SelectMaxMin(a,i,(i+j)/2,maxi,mini);

SelectMaxMin(a,((i+j)/2)+1,j,maxj,minj);

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余3页未读，立即下载

内容反馈

版权申诉

G11176593

粉丝: 6643
资源: 3万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip