图片网站推广,客户关系管理系统平台,郴州做网站seo,如何查看网站开发公司实验一 绪论
一、实验目的与要求
1#xff09;熟悉C/C语言#xff08;或其他编程语言#xff09;的集成开发环境#xff1b;
2#xff09;通过本实验加深对算法时间复杂度的理解#xff1b;
3#xff09;结合具体的问题分析算法时间复杂度。
二、实验内容
设计程…实验一 绪论
一、实验目的与要求
1熟悉C/C语言或其他编程语言的集成开发环境
2通过本实验加深对算法时间复杂度的理解
3结合具体的问题分析算法时间复杂度。
二、实验内容
设计程序实现统计一个班的学生成绩学生的人数可以设置3000、5000、8000、10000等测试数据要求自行设计至少两种排序算法实现如下四个功能记录每种算法的耗时结合数据结构的知识对两种算法的时间复杂度进行比较说明。
(1) 输入每个学生的学号并随机生成2门课程的成绩
(2) 计算每个学生的平均成绩和总成绩
(3) 按总成绩从高到低排名并按名次输出每个学生情况包括 学号各科成绩平均成绩总成绩排名
(4) 由键盘输入课程号输出该课程成绩在90分含90分以上且总分在前3名的学生情况要求能多次查询。
三、实验步骤
1程序中可能遇到的头文件如下
#includeWindows.h //windows头文件
#includeiostream //引入一个流类库
#includestdio.h //标准输入输出头文件
#includetime.h //导入时间库函数文件
2提示代码
int array_Sort[ARRAY_MAXSIZE]; //声明待排序的数组
int array_Sort2[ARRAY_MAXSIZE];
for(int i0;iARRAY_MAXSIZE;i){ //生成随机数组大小为10000
...... }
for(int j0;jARRAY_MAXSIZE;j){ //生成递减数组大小均为10000
...... }
clock_t start,end; //声明开始和结束的时间计数器
startclock(); //排序开始时间计数器
endclock(); //排序结束时间计数器 cout(double)(end-start) msendl;//排序的时间 3请将调试成功的源代码粘贴在下面 TEST #includeWindows.h //windows头文件
#includeiostream //引入一个流类库
#includestdio.h //标准输入输出头文件
#includetime.h //导入时间库函数文件
#includecstring
#includecstdlib
using namespace std;class Student{int ** student;//二维数组:指针的指针 int x,y;//坐标
public://构造Student(int temp0){xtemp;y5;studentnew int *[x];//坐标x int i0;for(i0;ix;i){student[i]new int [y];//坐标y }}//输出void Show(){int i0;for(i0;ix;i){cout学号student[i][0]科目一成绩student[i][1]科目二成绩student[i][2]平均成绩student[i][3]总成绩student[i][4]排名student[i][5]1endl; //student[i][5]初始化为i输出时候1}} //随机生成void Data(){int i0;for(i0;ix;i){student[i][0]i;//学号 student[i][1]rand()%100;//科目一成绩 student[i][2]rand()%100;//科目二成绩 student[i][3](student[i][1]student[i][2])/2;//平均分 student[i][4]student[i][1]student[i][2];//总分}} //总分排序冒泡 void Rank(){int *temp,i0,j0;clock_t start,end;//声明开始和结束的时间计数器startclock();//排序开始时间计数器for(i0;ix-1;i){//外层n个元素n-1次 for(j0;jx-i-1;j){//内层n个元素n-i次 if(student[j][4]student[j1][4]){tempstudent[j];student[j]student[j1];student[j1]temp;}}}endclock();//排序结束时间计数器cout冒泡排序法所用时间(double)(end-start) msendl;//排序的时间for(i0;ix;i){student[i][5]i;//初始化排名 }}//总分排序选择void rank(){int *temp,maxno,i0,j0;clock_t start,end;//声明开始和结束的时间计数器startclock();//排序开始时间计数器for(i0;ix-1;i){//x个数循环x-1次 maxnoi;//假设第i个最小 for(ji1;jx;j){if(student[j][4]student[maxno][4]){maxnoj;}}tempstudent[i];student[i]student[maxno];student[maxno]temp;}endclock();//排序结束时间计数器cout选择排序法所用时间(double)(end-start) msendl;//排序的时间for(i0;ix;i){student[i][5]i;//初始化排名 }}//第四问1.0 /*void Problem(int subject0){Student.rank();int num0;//统计总分前三名 int flag0;//标记符合条件存在情况 for(num0;num3;num){if(student[num][subject]90){//第i个人这门课符合条件cout学号student[num][0]科目一成绩student[num][1]科目二成绩student[num][2]平均成绩student[num][3]总成绩student[num][4]排名student[num][5]endl;flag1; }} if(flag0){cout该课程成绩在90分含90分以上且总分在前3名的学生不存在 endl;}}*//*//析构~Student(){int i0;for(i0;ix;i){delete [] student[i];student[i]NULL;//删除指针的指针 }delete [] student;studentNULL;//删除指针 }*///第四问2.0 void Problem(int subject0){int num0;//统计总分前三名的counter int flag0;//标记符合条件存在情况 for(num0;num3;num){if(student[num][subject]90){//第i个人这门课符合条件cout学号student[num][0]科目一成绩student[num][1]科目二成绩student[num][2]平均成绩student[num][3]总成绩student[num][4]排名student[num][5]1endl;flag1; }} if(flag0){cout该课程成绩在90分含90分以上且总分在前3名的学生不存在 endl;}}
};int main(){cout请输入学生人数;int myx;cinmyx;Student test(myx);//调用构造test.Data();//调用随机生成test.Rank();//调用冒泡test.Show();cout请输入查询次数;int checktime;cinchecktime;int time; for(time1;timechecktime;time){cout请输入查询科目科目一输入1科目二输入2;int sub;cinsub;test.rank();//调用选择 test.Problem(sub);//输出问题四的结果 }return 0;
}4运行结果分析
1.数组大小ARRAY_MAXSIZE为10000如下截图运行结果 2.数组大小ARRAY_MAXSIZE为8000如下截图运行结果 3.数组大小ARRAY_MAXSIZE为5000如下截图运行结果 4.数组大小ARRAY_MAXSIZE为3000如下截图运行结果 两种算法时间性能分析表 方法 最好情况 最坏情况 平均情况 冒泡排序 10000人277ms 8000人165ms 5000人53ms 3000人17ms 10000人281ms 8000人170ms 5000人57ms 3000人17ms 10000人279ms 8000人167.5ms 5000人55ms 3000人17ms 简单选择排序 10000人150ms 8000人87ms 5000人26ms 3000人9ms 10000人150ms 8000人96ms 5000人26ms 3000人10ms 10000人150ms 8000人91.5ms 5000人26ms 3000人9.5ms 请针对上表进行分析与说明
分析
在人为设置总人数为10000人、8000人、5000人、3000人的四个案例中冒泡排序法的运算时间均大于简单选择排序法的运算时间且总体来看冒泡排序法的运算时间是简单选择排序法的运算时间的1.5倍~2倍。
说明
为了分析上述表格的结果我们设元素个数为length对上述表格的两种排序算法作如下的简要理解
冒泡排序法运算法则为——从第一个值开始依次轮询相邻的两个数依次比较如果大于(正序排序)或者小于倒序排序则交换位置即每一次轮询都会把最大的一个数冒泡到最后轮询次数为length-1每次轮询的长度都会减1。
简单选择排序法运算法则为——从第一个值开始依次轮询每次轮询把当前值替换为最大值轮询次数为length-1每次轮询的长度都会减1。
通过对比我们容易发现两种排序算法的时间复杂度都为O(n²)但二者的排序理念和结果大不相同对此作以下两点分析与说明
首先从程序设计的思路来看冒泡排序法通过相邻两个元素的逐一对比从而进行大小排序而简单选择排序法是以当前元素为基准将其和后面的元素之一对比在一定程度上会使得相同值的元素比较过程中两个元素的相对前后顺序位置受到影响。因而冒泡排序法相比于简单选择排序法而言在算法的思路理解和具体的编程过程上更为简单且容易理解在实际运算的过程中更为稳定。
其次从运算时间的长短来看在内循环中冒泡排序法每次都要交换元素的顺序而简单选择排序法则只需要记录元素的下标在一轮的比较只需要换一次位置。因而冒泡排序法的效率比简单选择排序法的效率低。上述表格的四种案例冒泡排序法的运算时间是简单选择排序法的运算时间的1.5倍~2倍的具体运算结果也证实了这条结论。
综上所述在所需计算量较小或者是对运算时间无具体要求的情况下我们可以优先选择冒泡排序法进行实践在所需计算量较大或者是要求运算时间尽可能小的情况下我们可以优先选择简单选择排序法进行实践。 其他参考代码
#includeWindows.h //windows头文件
#includeiostream //引入一个流类库
#includestdio.h //标准输入输出头文件
#includetime.h //导入时间库函数文件
#includeiomanip
#includecstdlib#define ARRAY_MAXSIZE 5000 //定义学生的人数
#define STR_LENGTH 5
#define CLASS 2 //课程数量using namespace std;class Student{
private:string id;char classnum[CLASS];int scores[4];int rank;
public:Student();//学生信息的初始化void init1(int num);//产生随机数排序void init2(int num);//产生递减数列排序void setrank(int ran);int getrank();int getscore1();int getscore2();string getinfo();//显示学生的信息//运算符重载 friend bool operator(const Student s1,const Student s2);//比较总成绩friend bool operator(const Student s1,const Student s2);
};
Student::Student(){id2021;classnum[0]D;classnum[1]S;for(int i0;i4;i){scores[i]0;}rank0;
}
void Student::init1(int num){//随机//id初始化string tempto_string(num);//id初始化idstring(STR_LENGTH - temp.length(), 0);//前面补零idtemp;//成绩初始化for(int i0;iCLASS;i){scores[i]rand()%101;}scores[2](scores[0]scores[1])/2;scores[3]scores[0]scores[1];
}
void Student::init2(int num){//递减//id初始化string tempto_string(num);//id初始化idstring(STR_LENGTH - temp.length(), 0);//前面补零idtemp;//成绩初始化scores[0]100-0.01*num;scores[1]100-0.01*num;scores[2](scores[0]scores[1])/2;scores[3]scores[0]scores[1];
}void Student::setrank(int ran){rankran;
}int Student::getrank(){return rank;
}int Student::getscore1(){return scores[0];
}int Student::getscore2(){return scores[1];
}string Student::getinfo(){string info;string temp[4];for(int i0;i4;i){temp[i]to_string(scores[i]);}string str0string(3 - temp[0].length(), )temp[0];string str1string(3 - temp[1].length(), )temp[1];string str2string(3 - temp[2].length(), )temp[2];string str3string(3 - temp[3].length(), )temp[3];info学号id科目D成绩str0科目S成绩str1平均成绩str2总成绩str3排名to_string(rank);return info;
}bool operator(const Student s1,const Student s2){return s1.scores[3]s2.scores[3];
}
bool operator(const Student s1,const Student s2){return s1.scores[3]s2.scores[3];
} void bubble_sort(Student arr[]){ //冒泡排序//计算排序的时间clock_t start,end; //声明开始和结束的时间计数器startclock(); //排序开始时间计数器 int i, j;for (i 0; i ARRAY_MAXSIZE - 1; i){for (j 0; j ARRAY_MAXSIZE - 1 - i; j){if (arr[j] arr[j 1]){Student temp;temparr[j];arr[j]arr[j1];arr[j1]temp;} }}endclock(); //排序结束时间计数器cout当前排序方法为冒泡排序endl;cout*************************endl;cout排序时间为setfill( )setw(10)(double)(end-start) msendl;
}void insertion_sort(Student arr[]){ //插入排序//计算排序的时间clock_t start,end; //声明开始和结束的时间计数器startclock(); //排序开始时间计数器 for(int i1;iARRAY_MAXSIZE;i){Student keyarr[i];int ji-1;while((j0) (keyarr[j])){arr[j1]arr[j];j--;}arr[j1]key;}endclock(); //排序结束时间计数器cout当前排序方法为插入排序endl;cout*************************endl;cout排序时间为setfill( )setw(10)(double)(end-start) msendl;
}void selection_sort(Student arr[]){ //选择排序//计算排序的时间clock_t start,end; //声明开始和结束的时间计数器startclock(); //排序开始时间计数器 for (int i 0; i ARRAY_MAXSIZE - 1; i) {int min i;for (int j i 1; j ARRAY_MAXSIZE; j)if (arr[j] arr[min])min j;Student temp;temparr[i];arr[i]arr[min];arr[min]temp;}endclock(); //排序结束时间计数器cout当前排序方法为插入排序endl;cout*************************endl;cout排序时间为setfill( )setw(10)(double)(end-start) msendl;
}int main(){Student arrOfStu[ARRAY_MAXSIZE];while(1){//初始界面的展示cout当前学生人数为:setfill( )setw(15)ARRAY_MAXSIZE人endl;cout********************************endl;cout1.进行学生学号成绩随机初始化****endlendl;cout2.进行学生学号成绩递减初始化****endlendl;cout3.进行学生成绩的排序 ****endlendl;cout4.按成绩从高到低输出学生情况****endlendl;cout5.输入课程号输出优秀学生 ****endlendl;//输出该课程成绩在90分含90分以上且总分在前3名的学生情况要求能多次查询cout********************************endl;int cho;cincho;switch(cho){case 0:cout欢迎下次使用endl;//system(pause);return 0;break;case 1:srand((unsigned)time(NULL));for(int i0;iARRAY_MAXSIZE;i){arrOfStu[i].init1(i);}cout随机初始化完成endl;system(pause);system(cls);break;case 2:for(int i0;iARRAY_MAXSIZE;i){arrOfStu[i].init2(i);}cout递减初始化完成endl;system(pause);system(cls);break;case 3://排序的不同方法//bubble_sort(arrOfStu);//insertion_sort(arrOfStu);selection_sort(arrOfStu);for(int i0;iARRAY_MAXSIZE;i){arrOfStu[i].setrank(i1);}system(pause);system(cls);break;case 4:if(arrOfStu[0].getrank()!0){for(int i0;iARRAY_MAXSIZE;i){coutarrOfStu[i].getinfo()endl;}system(pause);system(cls);break;}else{cout成绩未排名请排名后再操作endl;system(pause);system(cls);break;}case 5:while(1){char c;cout请输入课程号\n输入E结束endl;cinc;if(cD){if(arrOfStu[0].getrank()!0){for(int i0;i3;i){if(arrOfStu[i].getscore1()90){coutarrOfStu[i].getinfo()endl;}}}else{cout成绩未排名请排名后再操作endl;system(pause);system(cls);break;}}else{if(cS){if(arrOfStu[0].getrank()!0){for(int i0;i3;i){if(arrOfStu[i].getscore2()90){coutarrOfStu[i].getinfo()endl;}}}else{cout成绩未排名请排名后再操作endl;system(pause);system(cls);break;}}else{if(cE){break;}else{cout输入错误请再次输入endlendl;}}}}system(pause);system(cls);break;default:cout输入错误请再次输入endl;system(pause);system(cls);break;}}return 0;
}
