欢迎来到天天文库
浏览记录
ID:53093252
大小:59.50 KB
页数:7页
时间:2020-04-01
《算法设计实验报告.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、算法设计与分析实验报告指导老师:王喜凤学号:089074106姓名:曹连娇班级:计084班实验一:题目:当问题规模时,快速排序和插入排序各需多少时间(100次平均结果)?写清机器配置,列出五种规模下各自需要的时间。按照下列表格提交:快速排序所需时间(ms)插入排序间(ms)两者相差多少N=1000.0000.0000N=10000,0141.8701.756N=100001.800122.740120.94N=10000023.50014786.35414762.854N=1000000302.000运行环境:运用VisualC++6.0编写和执行程序#defineN10000#incl
2、ude#includeusingnamespacestd;voidq_sort(inta[],longlow,longhigh){longi,j;intx;i=low;j=high;x=a[i];while(i=x&&i3、i=1;i4、d=clock();i_time=(double)(i_end-i_start);printf("%f",(double)(i_end-i_start));ii=ii+i_time;q_start=clock();q_sort(a,0,N-1);q_end=clock();q_time=(double)(q_end-q_start);qq=qq+q_time;}printf("%ld个随机数进行快速排序用时%6.0f毫秒",N,qq/100);printf("%ld个随机数进行插入排序用时%6.0f毫秒",N,ii/100);return0;}实验二:下表格式列出其中的五种情况,5、其中物品个数、背包容量、物品重量和物品价值要随机产生。物品个数N背包容量C物品重量Wi物品价值V最优值最优解所需时间(ms)28(5,10)(1,5)4(0,0.8)0217(9,8)(6,7)13(1,1)17657615(4,3,4,2,4,8)(2,4,5,2,9,5)21.25(0,1,1,1,1,0.25)16875318(8,4,10)(10,2,9)19(1,0,1)43812716(1,9,1,5,7,1,1)(3,7,3,9,6,10,1)32(1,0,1,1,1,1,1)34969代码如下:#include#include#i6、nclude#include"time.h"structgoodinfo{floatv;//物品的效益floatw;//物品的重量floatX;intflag;};//物品信息结构体voidInsertionsort(goodinfogoods[],intn){//插入排序,按vi/wi价值收益进行排序intj,i;for(j=2;j<=n;j++){goods[0]=goods[j];i=j-1;while(goods[0].v>goods[i].v){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}}//按物品效益,重量比7、值做升序排列voidbag(goodinfogoods[],floatM,intn){floatcu;inti,j;for(i=1;i<=n;i++)goods[i].X=0;cu=M;//背包剩余容量for(i=1;icu)//当该物品重量大与剩余容量跳出break;goods[i].X=1;cu=cu-goods[i].w;//确定背包新的剩余容量}if(i<=n)goods[i].X
3、i=1;i4、d=clock();i_time=(double)(i_end-i_start);printf("%f",(double)(i_end-i_start));ii=ii+i_time;q_start=clock();q_sort(a,0,N-1);q_end=clock();q_time=(double)(q_end-q_start);qq=qq+q_time;}printf("%ld个随机数进行快速排序用时%6.0f毫秒",N,qq/100);printf("%ld个随机数进行插入排序用时%6.0f毫秒",N,ii/100);return0;}实验二:下表格式列出其中的五种情况,5、其中物品个数、背包容量、物品重量和物品价值要随机产生。物品个数N背包容量C物品重量Wi物品价值V最优值最优解所需时间(ms)28(5,10)(1,5)4(0,0.8)0217(9,8)(6,7)13(1,1)17657615(4,3,4,2,4,8)(2,4,5,2,9,5)21.25(0,1,1,1,1,0.25)16875318(8,4,10)(10,2,9)19(1,0,1)43812716(1,9,1,5,7,1,1)(3,7,3,9,6,10,1)32(1,0,1,1,1,1,1)34969代码如下:#include#include#i6、nclude#include"time.h"structgoodinfo{floatv;//物品的效益floatw;//物品的重量floatX;intflag;};//物品信息结构体voidInsertionsort(goodinfogoods[],intn){//插入排序,按vi/wi价值收益进行排序intj,i;for(j=2;j<=n;j++){goods[0]=goods[j];i=j-1;while(goods[0].v>goods[i].v){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}}//按物品效益,重量比7、值做升序排列voidbag(goodinfogoods[],floatM,intn){floatcu;inti,j;for(i=1;i<=n;i++)goods[i].X=0;cu=M;//背包剩余容量for(i=1;icu)//当该物品重量大与剩余容量跳出break;goods[i].X=1;cu=cu-goods[i].w;//确定背包新的剩余容量}if(i<=n)goods[i].X
4、d=clock();i_time=(double)(i_end-i_start);printf("%f",(double)(i_end-i_start));ii=ii+i_time;q_start=clock();q_sort(a,0,N-1);q_end=clock();q_time=(double)(q_end-q_start);qq=qq+q_time;}printf("%ld个随机数进行快速排序用时%6.0f毫秒",N,qq/100);printf("%ld个随机数进行插入排序用时%6.0f毫秒",N,ii/100);return0;}实验二:下表格式列出其中的五种情况,
5、其中物品个数、背包容量、物品重量和物品价值要随机产生。物品个数N背包容量C物品重量Wi物品价值V最优值最优解所需时间(ms)28(5,10)(1,5)4(0,0.8)0217(9,8)(6,7)13(1,1)17657615(4,3,4,2,4,8)(2,4,5,2,9,5)21.25(0,1,1,1,1,0.25)16875318(8,4,10)(10,2,9)19(1,0,1)43812716(1,9,1,5,7,1,1)(3,7,3,9,6,10,1)32(1,0,1,1,1,1,1)34969代码如下:#include#include#i
6、nclude#include"time.h"structgoodinfo{floatv;//物品的效益floatw;//物品的重量floatX;intflag;};//物品信息结构体voidInsertionsort(goodinfogoods[],intn){//插入排序,按vi/wi价值收益进行排序intj,i;for(j=2;j<=n;j++){goods[0]=goods[j];i=j-1;while(goods[0].v>goods[i].v){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}}//按物品效益,重量比
7、值做升序排列voidbag(goodinfogoods[],floatM,intn){floatcu;inti,j;for(i=1;i<=n;i++)goods[i].X=0;cu=M;//背包剩余容量for(i=1;icu)//当该物品重量大与剩余容量跳出break;goods[i].X=1;cu=cu-goods[i].w;//确定背包新的剩余容量}if(i<=n)goods[i].X
此文档下载收益归作者所有