分治算法_精品文档

广东金融学院实验报告课程名称：算法设计与分析课程设计实验编号及实验名称实验二 分治算法系 别应用数学系姓 名许夏梦学 号071612117班 级0716121实验地点新电 605实验日期2025-9-23实验时数4指导老师骆世广同组其他成员成 绩一、实验目的及要求1、了解用分治法求解的问题：当要求解一个输入规模为 n，且 n 的取值相当大的问题时，假如问题可以分成 k 个不同子集合，得到 k 个不同的可独立求解的子问题，其中 1kn，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那么，对于这类问题分治法是十分有效的；2、掌握分治法的一般控制流程； DanC(p,q) Global n, A[1:n];integer m,p,q;// 1pqn if Small(p,q) then return G(p,q); else m=Divide(p,q);//pmq return Combine(DanC(p,m),DanC(m+1,q)); endif end DanC3、实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。二、实验环境及相关情况（包含使用软件、实验设备、主要仪器及材料等）使用软件：C++软件；使用实验设备：计算机：Intel(R);Pentium(R) 4 CPU 2.80GHz;2.79 GHz,0.99 GB 的内存；使用系统：Microsoft Windows XP;Professional;版本 2025；Service Pack 2.三、实验内容及步骤（包含简要的实验步骤流程）实验内容：1、 编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数；2、 输入 10 组相同的数据，验证排序结果和完成排序的比较次数；3、 与复杂性函数所计算的比较次数比较；4、 用表格列出比较结果；5、 给出文字分析。实验步骤：1、归并排序算法：void Merge(SeqList R，int low，int m，int high){//将两个有序的子文件 R[low..m)和 R[m+1..high]归并成一个有序的 //子文件 R[low..high] int i=low，j=m+1，p=0； //置初始值 RecType *R1； //R1 是局部向量，若 p 定义为此类型指针速度更快 R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))； if(! R1) //申请空间失败 Error("Insufficient memory available!")； while(i<=m&&j<=high) //两子文件非空时取其小者输出到 R1[p]上 R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]； while(i<=m) //若第 1 个子文件非空，则复制剩余记录到 R1 中 R1[p++]=R[i++]； while(j<=high) //若第 2 个子文件非空，则复制剩余记录到 R1 中 R1[p++]=R[j++]；...