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

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

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

3、t;templateint Partition(Type a,int p,int r) /以ap为基准元素，对数组ap:r进行划分 int i=p,j=r+1; Type x=ap; while(true) while(a+ix&ir); while(x=j) break; Swap(ai,aj); ap=aj; aj=x; return j;templatevoid QuickSort(Type a,int p,int r) /对数组ap:r进行快速排序 if(pr) int q=Partition(a,p,r); QuickSort(a,p,q-1); QuickSort(a,q+1,r)

4、; #endif / QUICKSORT_H_INCLUDEDmain.cpp#include #include QuickSort.husing namespace std;class Studentpublic: Student() name=noname; score=0; Student(string n,int s) name=n; score=s; bool operator scorescore; friend ostream& operator(ostream &out,Student &s);private: string name; int score;ostream& o

5、perator(ostream &out,Student &s) outs.name; return out;void MaxMm(Student a,int p,int r,Student &Max,Student &Min) Max=Min=ap; if(r-p+1=1) Min=Max=ar; if(r-p+1=2) if(ar2) int mid=(p+r)/2; Student max1,min1; MaxMm(a,p,mid,Max,Min); MaxMm(a,mid+1,r,max1,min1); if(Maxmax1) Max=max1; if(min1Min) Min=min

6、1; int main() Student a= Student(a,86),Student(b,43),Student(c,67),Student(d,82), Student(e,33),Student(f,75),Student(g,79),Student(h,59), Student(i,60),Student(j,95) ; Student Max,Min; MaxMm(a,0,9,Max,Min); cout成绩最高的学生：Maxendl; cout成绩最低的学生：Minendl;运行结果：实验总结 一直都觉得学算法设计与分析很难、很纠结，尤其是还要上机实践。开始的时候一点头绪都没有，好在有实验指导，至少找了个方向，而且第一题比较容易，而且也是第二题的基础，因此，在经过开始的纠结后，总算有点收获了，最后随着问题的解决，心情也随之豁然开朗，感觉很不错。