算法设计与分析实验1报告.doc
《算法设计与分析实验1报告.doc》由会员分享,可在线阅读,更多相关《算法设计与分析实验1报告.doc(4页珍藏版)》请在冰点文库上搜索。
湖南科技学院实验报告
系部
数学与计算科学
专业
信息与计算科学
成绩评定
班级
信计0902班
学号
200905002231
姓名
易丹
课程名称
算法设计与分析
实验时间
2012.3.09
实验编号
实验一
实验名称
分治与递归
实验环境
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
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]while(xif(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}templatevoidQuickSort(Typea[],intp,intr){//对数组a[p:r]进行快速排序if(p{intq=Partition(a,p,r);QuickSort(a,p,q-1);QuickSort(a,q+1,r);}}#endif//QUICKSORT_H_INCLUDEDmain.cpp#include#include"QuickSort.h"usingnamespacestd;classStudent{public:Student(){name="noname";score=0;}Student(stringn,ints){name=n;score=s;}booloperator<(Studentb){if(this->scorereturntrue;elsereturnfalse;}operatorint(){returnthis->score;}friendostream&operator<<(ostream&out,Student&s);private:stringname;intscore;};ostream&operator<<(ostream&out,Student&s){out<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]{Max=a[p];Min=a[r];}else{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(MaxMax=max1;if(min1Min=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),Student("i",60),Student("j",95)};StudentMax,Min;MaxMm(a,0,9,Max,Min);cout<<"成绩最高的学生:"<cout<<"成绩最低的学生:"<}运行结果:实验总结一直都觉得学算法设计与分析很难、很纠结,尤其是还要上机实践。开始的时候一点头绪都没有,好在有实验指导,至少找了个方向,而且第一题比较容易,而且也是第二题的基础,因此,在经过开始的纠结后,总算有点收获了,最后随着问题的解决,心情也随之豁然开朗,感觉很不错。
while(xif(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}templatevoidQuickSort(Typea[],intp,intr){//对数组a[p:r]进行快速排序if(p{intq=Partition(a,p,r);QuickSort(a,p,q-1);QuickSort(a,q+1,r);}}#endif//QUICKSORT_H_INCLUDEDmain.cpp#include#include"QuickSort.h"usingnamespacestd;classStudent{public:Student(){name="noname";score=0;}Student(stringn,ints){name=n;score=s;}booloperator<(Studentb){if(this->scorereturntrue;elsereturnfalse;}operatorint(){returnthis->score;}friendostream&operator<<(ostream&out,Student&s);private:stringname;intscore;};ostream&operator<<(ostream&out,Student&s){out<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]{Max=a[p];Min=a[r];}else{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(MaxMax=max1;if(min1Min=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),Student("i",60),Student("j",95)};StudentMax,Min;MaxMm(a,0,9,Max,Min);cout<<"成绩最高的学生:"<cout<<"成绩最低的学生:"<}运行结果:实验总结一直都觉得学算法设计与分析很难、很纠结,尤其是还要上机实践。开始的时候一点头绪都没有,好在有实验指导,至少找了个方向,而且第一题比较容易,而且也是第二题的基础,因此,在经过开始的纠结后,总算有点收获了,最后随着问题的解决,心情也随之豁然开朗,感觉很不错。
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{intq=Partition(a,p,r);QuickSort(a,p,q-1);QuickSort(a,q+1,r);}}#endif//QUICKSORT_H_INCLUDEDmain.cpp#include#include"QuickSort.h"usingnamespacestd;classStudent{public:Student(){name="noname";score=0;}Student(stringn,ints){name=n;score=s;}booloperator<(Studentb){if(this->scorereturntrue;elsereturnfalse;}operatorint(){returnthis->score;}friendostream&operator<<(ostream&out,Student&s);private:stringname;intscore;};ostream&operator<<(ostream&out,Student&s){out<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]{Max=a[p];Min=a[r];}else{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(MaxMax=max1;if(min1Min=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),Student("i",60),Student("j",95)};StudentMax,Min;MaxMm(a,0,9,Max,Min);cout<<"成绩最高的学生:"<cout<<"成绩最低的学生:"<}运行结果:实验总结一直都觉得学算法设计与分析很难、很纠结,尤其是还要上机实践。开始的时候一点头绪都没有,好在有实验指导,至少找了个方向,而且第一题比较容易,而且也是第二题的基础,因此,在经过开始的纠结后,总算有点收获了,最后随着问题的解决,心情也随之豁然开朗,感觉很不错。
intq=Partition(a,p,r);
QuickSort(a,p,q-1);
QuickSort(a,q+1,r);
#endif//QUICKSORT_H_INCLUDED
main.cpp
#include
#include"QuickSort.h"
usingnamespacestd;
classStudent
public:
Student()
name="noname";
score=0;
Student(stringn,ints)
name=n;
score=s;
booloperator<(Studentb)
if(this->scorereturntrue;elsereturnfalse;}operatorint(){returnthis->score;}friendostream&operator<<(ostream&out,Student&s);private:stringname;intscore;};ostream&operator<<(ostream&out,Student&s){out<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]{Max=a[p];Min=a[r];}else{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(MaxMax=max1;if(min1Min=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),Student("i",60),Student("j",95)};StudentMax,Min;MaxMm(a,0,9,Max,Min);cout<<"成绩最高的学生:"<cout<<"成绩最低的学生:"<}运行结果:实验总结一直都觉得学算法设计与分析很难、很纠结,尤其是还要上机实践。开始的时候一点头绪都没有,好在有实验指导,至少找了个方向,而且第一题比较容易,而且也是第二题的基础,因此,在经过开始的纠结后,总算有点收获了,最后随着问题的解决,心情也随之豁然开朗,感觉很不错。
returntrue;
else
returnfalse;
operatorint()
returnthis->score;
friendostream&operator<<(ostream&out,Student&s);
private:
stringname;
intscore;
};
ostream&operator<<(ostream&out,Student&s)
out<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]{Max=a[p];Min=a[r];}else{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(MaxMax=max1;if(min1Min=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),Student("i",60),Student("j",95)};StudentMax,Min;MaxMm(a,0,9,Max,Min);cout<<"成绩最高的学生:"<cout<<"成绩最低的学生:"<}运行结果:实验总结一直都觉得学算法设计与分析很难、很纠结,尤其是还要上机实践。开始的时候一点头绪都没有,好在有实验指导,至少找了个方向,而且第一题比较容易,而且也是第二题的基础,因此,在经过开始的纠结后,总算有点收获了,最后随着问题的解决,心情也随之豁然开朗,感觉很不错。
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]{Max=a[p];Min=a[r];}else{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(MaxMax=max1;if(min1Min=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),Student("i",60),Student("j",95)};StudentMax,Min;MaxMm(a,0,9,Max,Min);cout<<"成绩最高的学生:"<cout<<"成绩最低的学生:"<}运行结果:实验总结一直都觉得学算法设计与分析很难、很纠结,尤其是还要上机实践。开始的时候一点头绪都没有,好在有实验指导,至少找了个方向,而且第一题比较容易,而且也是第二题的基础,因此,在经过开始的纠结后,总算有点收获了,最后随着问题的解决,心情也随之豁然开朗,感觉很不错。
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(MaxMax=max1;if(min1Min=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),Student("i",60),Student("j",95)};StudentMax,Min;MaxMm(a,0,9,Max,Min);cout<<"成绩最高的学生:"<cout<<"成绩最低的学生:"<}运行结果:实验总结一直都觉得学算法设计与分析很难、很纠结,尤其是还要上机实践。开始的时候一点头绪都没有,好在有实验指导,至少找了个方向,而且第一题比较容易,而且也是第二题的基础,因此,在经过开始的纠结后,总算有点收获了,最后随着问题的解决,心情也随之豁然开朗,感觉很不错。
Max=max1;
if(min1Min=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),Student("i",60),Student("j",95)};StudentMax,Min;MaxMm(a,0,9,Max,Min);cout<<"成绩最高的学生:"<cout<<"成绩最低的学生:"<}运行结果:实验总结一直都觉得学算法设计与分析很难、很纠结,尤其是还要上机实践。开始的时候一点头绪都没有,好在有实验指导,至少找了个方向,而且第一题比较容易,而且也是第二题的基础,因此,在经过开始的纠结后,总算有点收获了,最后随着问题的解决,心情也随之豁然开朗,感觉很不错。
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),
Student("i",60),Student("j",95)
StudentMax,Min;
MaxMm(a,0,9,Max,Min);
cout<<"成绩最高的学生:
"<cout<<"成绩最低的学生:"<}运行结果:实验总结一直都觉得学算法设计与分析很难、很纠结,尤其是还要上机实践。开始的时候一点头绪都没有,好在有实验指导,至少找了个方向,而且第一题比较容易,而且也是第二题的基础,因此,在经过开始的纠结后,总算有点收获了,最后随着问题的解决,心情也随之豁然开朗,感觉很不错。
cout<<"成绩最低的学生:
"<}运行结果:实验总结一直都觉得学算法设计与分析很难、很纠结,尤其是还要上机实践。开始的时候一点头绪都没有,好在有实验指导,至少找了个方向,而且第一题比较容易,而且也是第二题的基础,因此,在经过开始的纠结后,总算有点收获了,最后随着问题的解决,心情也随之豁然开朗,感觉很不错。
运行结果:
实验总结
一直都觉得学算法设计与分析很难、很纠结,尤其是还要上机实践。
开始的时候一点头绪都没有,好在有实验指导,至少找了个方向,而且第一题比较容易,而且也是第二题的基础,因此,在经过开始的纠结后,总算有点收获了,最后随着问题的解决,心情也随之豁然开朗,感觉很不错。
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2