算法设计与分析实验1报告.doc

《算法设计与分析实验1报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、湖南科技学院实验报告系部数学与计算科学专业信息与计算科学成绩评定班级信计0902班学号1姓名易丹课程名称算法设计与分析实验时间2012.3.09实验编号实验一实验名称分治与递归实验环境D315、一台电脑、Codeblocks10.05实验目的1.理解递归的概念。2.掌握设计有效算法的分治策略。3.掌握C++面向对象编程方法。实验内容（①算法、程序、步骤和方法②输入、输出、实验结果③实验结果分析）实验内容：已知有某班学生的成绩如下：姓名abcdefghij成绩86436782337579596095在程序中创建一个学生对象数组并初始化数据，完成如

2、下编程任务。⑴找出成绩排名第4的学生，输出其姓名。要求：①编写功能较为完善的学生类，重载必要的运算符；②使用快速排序的方法。⑵使用分治法找出成绩最高和成绩最低的学生，输出他们的姓名。实验要求：①实验报告只写实验⑵。②写出算法思想、主要程序代码、算法复杂性分析。实验（2）的步骤、算法及运行结果：⑴打开Codeblocks10.05，编辑如下分治法程序,运行即可得到成绩最高和成绩最低的学生姓名。QuickSort.h#ifndefQUICKSORT_H_INCLUDED#defineQUICKSORT_H_INCLUDEDtemplate

3、nameType>voidSwap(Type&a,Type&b){Typet=b;b=a;a=t;}templateintPartition(Typea[],intp,intr){//以a[p]为基准元素，对数组a[p:r]进行划分inti=p,j=r+1;Typex=a[p];while(true){while(a[++i]=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}template

4、meType>voidQuickSort(Typea[],intp,intr){//对数组a[p:r]进行快速排序if(p#include"QuickSort.h"usingnamespacestd;classStudent{public:Student(){name="noname";score=0;}St

5、udent(stringn,ints){name=n;score=s;}booloperator<(Studentb){if(this->scorescore;}friendostream&operator<<(ostream&out,Student&s);private:stringname;intscore;};ostream&operator<<(ostream&out,Student&s){out<

6、;returnout;}voidMaxMm(Studenta[],intp,intr,Student&Max,Student&Min){Max=Min=a[p];if(r-p+1==1)Min=Max=a[r];if(r-p+1==2){if(a[r]2){intmid=(p+r)/2;Studentmax1,min1;MaxMm(a,p,mid,Max,Min);MaxMm(a,mid+1,r,max1,min1);if(M

7、ax

8、<