算法分析报告与设计实验报告材料

1、算法设计与分析学院：计算机科学与技术学号：129074106姓名：张淼淼2014 11 141、当问题规模N _100时，快速排序和插入排序各需多少时间？写清机器配置，列出五种规模下各自需要的时间。按照下列表格提交：快速排序所需时间(ms)插入排序所需时间(ms)两者相差多少N=1000.006000.019000-0.013000N=10000.0740000.724000-0.650000N=100000.03200064.657000-64.625000N=10000013.30000050.900000-37.600000N=100000053.500000117.700000-64.

2、200000机器配置：Win dow 732 位Cpu： Inter(R) Core(TM) i3-2120 cpu3.30GHzAMD Radeon HD 6450 Graphicsraw 苣理员：C:Windowssytem52cmd.exe - sfDebugsf.exeMicrosoft Uindous 版本 6,1.76011版、权所有 W 2089 Microsoft CorporationQ保留所有权利*C： MJsers MldninistiatopE：E： sf DebugXsf - exe请输入问题的规模：100E：sfDebugXsf-exe请输入问题的规模:10000.

3、0748000.724000aw 皆理員：C:Windows syste m 3 2cmd. exeMicrosoft Uindous【椒本 版权所有200? Hicrosof t Carpofat ion保留所有权刑；:s F De butrXsf. exe请输入冋題的规模：10000速入种-3- _JJ两的的相:-64.6250AB64.657000：IJ广SB IT理员：C:Wi ndowssystem 3 2cmd. exeIf回licrosof t U in do us 龈本 & -1.7&B1 版权所有200? tlicrosoft Corporationo保留所有权刑&1:sfD

4、ebugXsf.exe情输入问題的规横：100000的的相疋:-37,t0PO0B13.30600050.900000sfDehugXsf.exe请输入问題的规模：佃鉅盹0速入种lkjLHJlm暑疋观 %1/ H- 鑫20 单单4.53.5000117.700000程序：#in clude#in clude#in clude#in clude int a1000000;int b1000000;void QuickSort(i nt low ,int high)long i,j;int x;i=low;j=high;x=ai;while(i=x&ij) j-;ai=aj;while(ai=x&

5、ij) i+;aj=ai;ai=x;if(low(j+1)QuickSort(j+1,high);void Binaryin sertSort(i nt len gth)in t low,high,mid;int i,j,m;/m为保存待插入的元素for(i=1;ile ngth;i+)m=bi;low=0;high=i-1;/ 设置初始区while(low=bmid)low=mid+1;elsehigh=mid-1;for(j=i-1;j=high+1;j-)/high为插入位置bj+1=bj;/ 后移元素，留出插入的空位 bhigh+1=m;/将元素插入正确的位置void mai n()t

6、ime_t start,finish;/time_t相当于 longdouble betwee n_time1,betwee n_time2,betwee n_time;/1表示快速排序所需时间，2表示插入排序所需时间，between_time表示两种排序之间的差值struct _timeb timebuffer1,timebuffer2;int startm,fi ni shm;double total1=0,total2=0;/1表示规模为N时，快速排序所需的累计时间，2表示规模为N是，插入排序所需的累计时间int N,i,j;/N 表示问题规模prin tf(n请输入问题的规模：”)；s

7、ca nf(%d,&N);/对一堆数据进行排序，排序1000次,求其排序的平均时间for(i=0;i1000;i+)sran d(u nsig ned)time(NULL);/对每次的排序进行设置随机种子(即编号)for(j=0;jN;j+)aj=ra nd();bj=aj;/快速排序_ftime( &timebuffer1);计算当前时间startm=litm;/start=timebuffer1.time;QuickSort(0,N-1);/ prin tf(n快速排序之后的数据为:);/for(i=0;iN;i+)/ / prin tf(%d ,ai);/

8、_ftime( &timebuffer1);fini shm=litm;fini sh=timebuffer1.time;between_time1=difftime(fi ni sh,start);/找出时间差betwee n_time1=1000*betwee n_time1+fi nishm-startm;total仁total1+betwee n_time1;/插入排序_ftime( &timebuffer2);startm=litm;start=timebuffer2.time;Bin aryl nsertSort(N);/

9、prin tf(n插入排序之后的数据为:);for(i=0;if sDebugFs .exe该背包的容量为：F=l 里管理员；匚;Wiri dom 3 2cmd. exe版权所有 电c 2009 Microsoft CarporationB青输入物品个数假设不超过1盹：2随机产生的物品重量/介值:”胸朋,26.0000&.00003.0000和品价值12.0000最优值为：38.0300该袂所需时间为：1 - 00000000背包程序#in clude#in clude#in clude#in cludedouble W100;重量表示每个物品的单价double V100;价值double u

10、n it_price100;void QuickSort(i nt low ,int high)/对单价进行排序long i,j;double x;double w,v;i=low;j=high;x=un it_pricei;w=Wi;v=Vi;while(i=x&ij) j-;un it_pricei=un it_pricej;Wi=Wj;将重量，价值和单价的下标始终统一Vi=Vj;while( uni t_pricei=x&ij) i+;un it_pricej=un it_pricei;Wj=Wi;Vj=Vi;un it_pricei=x;Wi=w;Vi=v;if(low(j+1)Qui

11、ckSort(j+1,high);void mai n()time_t start,fi ni sh;double betwee n_time;int startm,fi ni shm;struct _timeb timebuffer;int N,i,j;/N 表示物品个数double sum=O,C,best_value=O;printf(n请输入物品个数(假设不超过100): ”)；sca nf(%d,&N);/随机产生物品重量以及价值sran d( un sig ned)time(NULL);printf(n随机产生的物品重量，价值：);for(i=0;iN;i+)Wi=rand()%1

12、0+1;重量产生的在 10以内Vi=rand()%100+1; 价值在 100 以内prin tf(n%6.4lf , %6.4lf,Wi,Vi);for(i=0;iN;i+)sum=sum+Wi;C=sum/3+1;将背包容量设为所有物品重量的三分之一加1prin tf(nn该背包的容量为：6.4lf,C);/从此处开始计算时间_ftime(&timebuffer);startm=litm;start=timebuffer.time;for(i=0;i=0;i-)if(Ci;j-)prin tf(n%6.4lf%6.4lf,Wj,Vj);best_value=be

13、st_value+Vj;prin tf(n%6.4lf%6.4lf,C,C*u nit_pricei);best_value=best_value+C* uni t_pricei;prin tf(nn最优值为：6.4lf,best_value);/计算时间结束_ftime(&timebuffer);fin ishm=litm;fini sh=timebuffer.time;betwee n_time=difftime(fi nish,start)*1000+fi nishm-startm;prin tf(nn该次所需时间为：%6.8lfnn,between_time

14、);3趣味矩阵：#in cludemai n()char a100100;int i,j,n;sca nf(%d,&n);for(i=1;i=n ;i+)for(j=1;j=n ;j+)if(i=j)|(i+j=n+1) aij=A; else if(ij&i+jj&i+jj&i+j n+1) aij=D; else aij=4;for(i=1;i=n ;i+)for(j=1;j=n ;j+)prin tf(%c ,aij);prin tf(n); D:MSDev98MyPnDjectsaaDebLigaa.exeBBBBADDDDBBBACADDDBBACCCADDftD D A cant

15、inue4请仔细阅读题目描述、你的任务及提示信息 题目描述：某校的惯例是在每学期的期末考试之后发放奖学金。 件各自不同：发放的奖学金共有五种， 获取的条1）院士奖学金，每人8000元，期末平均成绩高于 1篇或1篇以上论文的学生均可获得；2）五四奖学金，每人 4000元，期末平均成绩高于 于80分（80）的学生均可获得；3）成绩优秀奖，每人 2000元，期末平均成绩高于4）西部奖学金，每人1000元，期末平均成绩高于 得；80分（80），并且在本学期内发表85分（85），并且班级评议成绩高90分（90）的学生均可获得；85分（85）的西部省份学生均可获5）班级贡献奖，每人850元，班级评议成绩高

16、于80分（80）的学生干部均可获得;每名学生也可以同时获得82分，同时他还是一位学生4850 元。只要符合条件就可以得奖，每项奖学金的获奖人数没有限制,多项奖学金。例如姚林的期末平均成绩是87分，班级评议成绩干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是你的任务：现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。并给出实现代码和5组实验数据。输入格式：输入的第一行是一个整数 N（ 1 = N = 100 ），表示学生的总数。接下来的N行每行是一位学生的数据，从左向右依次是姓名， 期末平均成绩，班级评议成绩，是否是学生干部， 是否是西

17、部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成绩都是0到100之间的整数（包括 0和100）;是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是 0到10的整数（包括0和10）。每两个相邻数据项之间用一个空格 分隔。输出格式：输出包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。第三行是这 N个学生获得的奖学金的总数。样例输入：4YaoL in 87 82 Y N 0Che nRuiyi 88 78 N Y 1LiXin 92 88 N N 0Zha ngQin 83 87 Y N 1样例输出：Che nRuiyi900028700程序：#in cludeusing n amespace std;int mai n()int i,j, n,q m,py,lw,prize,max=0;long total=0;char a20, nam