算法设计与分析实验1报告Word格式.doc
《算法设计与分析实验1报告Word格式.doc》由会员分享，可在线阅读，更多相关《算法设计与分析实验1报告Word格式.doc（4页珍藏版）》请在冰点文库上搜索。
实验环境
D315、一台电脑、Codeblocks10.05
实验目的
1.理解递归的概念。
2.掌握设计有效算法的分治策略。
3.掌握C++面向对象编程方法。
实验内容（①算法、程序、步骤和方法②输入、输出、实验结果③实验结果分析）
实验内容：
已知有某班学生的成绩如下：
a
b
c
d
e
f
g
h
i
j
成绩
86
43
67
82
33
75
79
59
60
95
在程序中创建一个学生对象数组并初始化数据，完成如下编程任务。
⑴找出成绩排名第4的学生，输出其姓名。
要求：
①编写功能较为完善的学生类，重载必要的运算符；
②使用快速排序的方法。
⑵使用分治法找出成绩最高和成绩最低的学生，输出他们的姓名。
实验要求：
①实验报告只写实验⑵。
②写出算法思想、主要程序代码、算法复杂性分析。
实验
（2）的步骤、算法及运行结果：
⑴打开Codeblocks10.05，编辑如下分治法程序,运行即可得到成绩最高和成绩最低的学生姓名。
QuickSort.h
#ifndefQUICKSORT_H_INCLUDED
#defineQUICKSORT_H_INCLUDED
template<
typenameType>
voidSwap（Type&
a,Type&
b）
{
Typet=b;
b=a;
a=t;
}
intPartition（Typea[],intp,intr）
//以a[p]为基准元素，对数组a[p:
r]进行划分
inti=p,j=r+1;
Typex=a[p];
while（true）
{
while（a[++i]<
x&
&
i<
r）;
while（x<
a[--j]）;
if（i>
=j）
break;
Swap（a[i],a[j]）;
}
a[p]=a[j];
a[j]=x;
returnj;
voidQuickSort（Typea[],intp,intr）
//对数组a[p:
r]进行快速排序
if（p<
r）
intq=Partition（a,p,r）;
QuickSort（a,p,q-1）;
QuickSort（a,q+1,r）;
#endif//QUICKSORT_H_INCLUDED
main.cpp
#include<
iostream>
#include"
QuickSort.h"
usingnamespacestd;
classStudent
public:
Student（）
name="
noname"
;
score=0;
Student（stringn,ints）
name=n;
score=s;
booloperator<
（Studentb）
if（this->
score<
b.score）
returntrue;
else
returnfalse;
operatorint（）
returnthis->
score;
friendostream&
operator<
<
（ostream&
out,Student&
s）;
private:
stringname;
intscore;
};
ostream&
s）
out<
s.name;
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]<
a[p]）
{
Max=a[p];
Min=a[r];
}
Max=a[r];
Min=a[p];
if（r-p+1>
2）
intmid=（p+r）/2;
Studentmax1,min1;
MaxMm（a,p,mid,Max,Min）;
MaxMm（a,mid+1,r,max1,min1）;
if（Max<
max1）
Max=max1;
if（min1<
Min=min1;
intmain（）
Studenta[]={Student（"
a"
86）,Student（"
b"
43）,Student（"
c"
67）,Student（"
d"
82）,
Student（"
e"
33）,Student（"
f"
75）,Student（"
g"
79）,Student（"
h"
59）,
i"
60）,Student（"
j"
95）
};
StudentMax,Min;
MaxMm（a,0,9,Max,Min）;
cout<
"
成绩最高的学生：
Max<
endl;
成绩最低的学生：
Min<
运行结果：
实验总结
一直都觉得学算法设计与分析很难、很纠结，尤其是还要上机实践。
开始的时候一点头绪都没有，好在有实验指导，至少找了个方向，而且第一题比较容易，而且也是第二题的基础，因此，在经过开始的纠结后，总算有点收获了，最后随着问题的解决，心情也随之豁然开朗，感觉很不错。
升级会员 