算法设计实验报告.doc

《算法设计实验报告.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&&i

3、i=1;i

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