《算法分析报告与设计实验报告材料.doc》由会员分享，可在线阅读，更多相关《算法分析报告与设计实验报告材料.doc（19页珍藏版）》请在三一文库上搜索。
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:Windowssy£tem52cmd.exe - sfDebugsf.exeMicrosoft Uindous 版本 6,1.76011版、权所有 W 2089 Microsoft CorporationQ保留所有权利*C： MJsers Mldninisti'atop>E：E： >sf DebugXsf - exe请输入问题的规模：100E：>sfDebu
3、gXsf-exe请输入问题的规模:10000.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
4、 版权所有200? tlicrosoft Corporationo保留所有权刑&1:>sfDebugXsf.exe情输入问題的规横：100000的的相疋:-37,t0PO0B13.30600050.900000>sfDehugXsf.exe请输入问題的规模：佃鉅盹0速入种lkjLHJlm暑疋观 %1/ H- 鑫20 单单4.53.50»»00117.700000程序：#in clude<stdio.h>#in clude<stdlib.h>#in clude<time.h>#in clude<systimeb.h
5、> int a1000000;int b1000000;void QuickSort(i nt low ,int high)long i,j;int x;i=low;j=high;x=ai;while(i<j)while(aj>=x&&i<j) j-;ai=aj;while(ai<=x&&i<j) i+;aj=ai;ai=x;if(low<(i-1)QuickSort(low,i-1);if(high>(j+1)QuickSort(j+1,high);void Binaryin sertSort(i nt len
6、gth)in t low,high,mid;int i,j,m;/m为保存待插入的元素for(i=1;i<le ngth;i+)m=bi;low=0;high=i-1;/ 设置初始区while(low<=high)mid=(low+high)/2;if(m>=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()time_t start,finish;/time_t相当于 longdoub
7、le 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请输入问题的规模：”)；sca nf("%d",&N);/对一
8、堆数据进行排序，排序1000次,求其排序的平均时间for(i=0;i<1000;i+)sran d(u nsig ned)time(NULL);/对每次的排序进行设置随机种子(即编号)for(j=0;j<N;j+)aj=ra nd();bj=aj;/快速排序_ftime( &timebuffer1);计算当前时间startm=timebuffer1.millitm;/start=timebuffer1.time;QuickSort(0,N-1);/ prin tf("n快速排序之后的数据为:");/for(i=0;i<N;i+)/ / prin t
9、f("%d ",ai);/ _ftime( &timebuffer1);fini shm=timebuffer1.millitm;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=timebuffer2.millitm;start=timebuff
10、er2.time;Bin aryl nsertSort(N);/prin tf("n插入排序之后的数据为:");for(i=0;i<N;i+)/ prin tf("%d ”,bi);/ _ftime( &timebuffer2);fin ishm=timebuffer2.millitm;fini sh=timebuffer2.time;betwee n_time2=difftime(fi nish,start);betwee n_time2=betwee n_time2*1000+fi ni shm-startm;/ total2=total2+be
11、tween_time2;prin tf("n快速排序的时间(以毫秒为单位)是：6.6f",total1/1000);prin tf("n插入排序的时间(以毫秒为单位)是：6.6f",total2/1000);between_time=total1/1000-total2/1000;prin tf("n两种排序相差的时间是：%6.6fnn",between_time);2用贪心算法实现背包问题，按下表格式列出其中的五种情况，其中物品个数、背包容量、 物品重量和物品价值要随机产生。物品个数N背包容量C物品重量Wi物品价值Vi最优值最优解所
12、需时间(ms)25.00002.000026.00002.000038.00001.000000010.000040.000026.000003.000012.000038.333310.000021.00003.0000 58.000092.37041.00000003.000058.00005.3333 34.730409.000058.000049.00002.000064.00002.0000160.0004.000000010.00002.000064.0000005.00002.00007.00007.000096.000096.0000510.66674.000076.00004
13、.0000163.7035.00000009.000053.000076.0000704.00008.00004.00006.000014.000072.00004.000072.00002.666715.7037613.66676.000042.00004.0000134.6665.00000004.000050.000050.0000707.000066.00007.00009.000045.000066.00005.00007.00002.66677.000048.000018.6667-X>f sDebugFs .exe该背包的容量为：F=l 里管理员；匚;Wiri dom 3
14、2cmd. exe版权所有 电c> 2009 Microsoft CarporationB青输入物品个数£假设不超过1盹：2随机产生的物品重量/介值:”胸朋,26.0000&.00003.0000和品价值12.0000最优值为：38.0300该袂所需时间为：1 - 00000000背包程序#in clude<stdio.h>#in clude<stdlib.h>#in clude<time.h>#in clude<systimeb.h>double W100;重量表示每个物品的单价double V100;价值double
15、un 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<j)while( uni t_pricej>=x&&i<j) j-;un it_pricei=un it_pricej;Wi=Wj;将重量，价值和单价的下标始终统一Vi=Vj;while( uni t_pricei<=x&&i<j) i+;un it_pricej=un i
16、t_pricei;Wj=Wi;Vj=Vi;un it_pricei=x;Wi=w;Vi=v;if(low<(i-1)QuickSort(low,i-1);if(high>(j+1)QuickSort(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): ”)；
17、sca nf("%d",&N);/随机产生物品重量以及价值sran d( un sig ned)time(NULL);printf("n随机产生的物品重量，价值：");for(i=0;i<N;i+)Wi=rand()%10+1;重量产生的在 10以内Vi=rand()%100+1; 价值在 100 以内prin tf("n%6.4lf , %6.4lf",Wi,Vi);for(i=0;i<N;i+)sum=sum+Wi;C=sum/3+1;将背包容量设为所有物品重量的三分之一加1prin tf("nn该背
18、包的容量为：6.4lf",C);/从此处开始计算时间_ftime(&timebuffer);startm=timebuffer.millitm;start=timebuffer.time;for(i=0;i<N;i+)un it_pricei=Vi/Wi;QuickSort(0,N-1);对单价进行排序(升序)for(i=N-1;i>=0;i-)if(C<=Wi)break;elseC=C-Wi;prin tf("nn最优解如下：");printf("n物品重量物品价值");for(j=N-1;j>i;j-)pr
19、in tf("n%6.4lf%6.4lf",Wj,Vj);best_value=best_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=timebuffer.millitm;fini sh=timebuffer.time;betwee n_time=difft
20、ime(fi nish,start)*1000+fi nishm-startm;prin tf("nn该次所需时间为：%6.8lfnn",between_time);3趣味矩阵：#in clude<stdio.h>mai 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(i<j&&i+j<n+1) aij=
21、9;B' else if(i>j&&i+j< n+1) aij=C;else if(i>j&&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.exe'BBBBADDDDBBBACADDDBBACCCADDftD D A cant inue4请仔细
22、阅读题目描述、你的任务及提示信息 题目描述：某校的惯例是在每学期的期末考试之后发放奖学金。 件各自不同：发放的奖学金共有五种， 获取的条1）院士奖学金，每人8000元，期末平均成绩高于 1篇或1篇以上论文的学生均可获得；2）五四奖学金，每人 4000元，期末平均成绩高于 于80分（80）的学生均可获得；3）成绩优秀奖，每人 2000元，期末平均成绩高于4）西部奖学金，每人1000元，期末平均成绩高于 得；80分（80），并且在本学期内发表85分（85），并且班级评议成绩高90分（90）的学生均可获得；85分（85）的西部省份学生均可获5）班级贡献奖，每人850元，班级评议成绩高于80分（80）
23、的学生干部均可获得;每名学生也可以同时获得82分，同时他还是一位学生4850 元。只要符合条件就可以得奖，每项奖学金的获奖人数没有限制,多项奖学金。例如姚林的期末平均成绩是87分，班级评议成绩干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是你的任务：现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。并给出实现代码和5组实验数据。输入格式：输入的第一行是一个整数 N（ 1 = N = 100 ），表示学生的总数。接下来的N行每行是一位学生的数据，从左向右依次是姓名， 期末平均成绩，班级评议成绩，是否是学生干部， 是否是西部省份学生，以及
24、发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成绩都是0到100之间的整数（包括 0和100）;是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是 0到10的整数（包括0和10）。每两个相邻数据项之间用一个空格 分隔。输出格式：输出包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。第三行是这 N个学生获得的奖学金的总数。样例输入：4YaoL in 87 82 Y N 0Che nRuiyi
25、 88 78 N Y 1LiXin 92 88 N N 0Zha ngQin 83 87 Y N 1样例输出：Che nRuiyi900028700程序：#in clude<iostream>using n amespace std;int mai n()int i,j, n,q m,py,lw,prize,max=0;long total=0;char a20, name20,xb,gb;cin»n;for(i=1;i<=n ;i+)cin> >a»qm>>py>>gb>>xb»lw; prize
26、=O;if(qm>80)&&(lw>0) prize+=8000;if(qm>85)&&(py>80) prize+=4000;if(qm>90) prize+=2000;if(qm>85) &&(xb='Y') prize+=1000; if(py>80) &&(gb='Y') prize+=850;total+=prize;if(prize>max)max=prize;for(j=0;j<20;j+)namej=aj;cout< <n ame<<e ndl<<max<<e ndl<<total;retur n 0;