《算法分析与设计实验报告资料》由会员分享，可在线阅读，更多相关《算法分析与设计实验报告资料（14页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析 学院：计算机科学与技术学号：129074106姓名：张淼淼 2014 11 14 1、 当问题规模时，快速排序和插入排序各需多少时间？写清机器配置，列出五种规模下各自需要的时间。按照下列表格提交：快速排序所需时间(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.20
2、0000机器配置：Window 7 32位Cpu：Inter(R) Core(TM) i3-2120 cpu3.30GHzAMD Radeon HD 6450 Graphics程序：#include#include#include#includeint a1000000;int b1000000;void QuickSort(int low ,int high)long i,j;int x;i=low;j=high;x=ai;while(i=x&ij) j-; ai=aj; while(ai=x&ij) i+; aj=ai;ai=x;if(low(j+1) QuickSort(j+1,high
3、);void BinaryInsertSort(int length)int low,high,mid;int i,j,m;/m为保存待插入的元素for(i=1;ilength;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 main()time_t start,finish;/time_t 相当于longdouble between
4、_time1,between_time2,between_time; /1表示快速排序所需时间，2表示插入排序所需时间，between_time表示两种排序之间的差值struct _timeb timebuffer1,timebuffer2;int startm,finishm;double total1=0,total2=0; /1表示规模为N时，快速排序所需的累计时间，2表示规模为N是，插入排序所需的累计时间int N,i,j;/N表示问题规模printf(n请输入问题的规模：);scanf(%d,&N); /对一堆数据进行排序，排序1000次,求其排序的平均时间for(i=0;i1000
5、;i+) srand(unsigned)time(NULL);/对每次的排序进行设置随机种子（即编号） for(j=0;jN;j+) aj=rand(); bj=aj; /快速排序 _ftime(&timebuffer1);/计算当前时间 startm=timebuffer1.millitm;/ start=timebuffer1.time; QuickSort(0,N-1); / printf(n快速排序之后的数据为:); /for(i=0;iN;i+) / / printf(%d ,ai); / _ftime(&timebuffer1); finishm=timebuffer1.milli
6、tm; finish=timebuffer1.time; between_time1=difftime(finish,start);/找出时间差 between_time1=1000*between_time1+finishm-startm; total1=total1+between_time1; / 插入排序 _ftime(&timebuffer2); startm=timebuffer2.millitm; start=timebuffer2.time; BinaryInsertSort(N); /printf(n插入排序之后的数据为:); /for(i=0;iN;i+) / / prin
7、tf(%d ,bi); / _ftime(&timebuffer2); finishm=timebuffer2.millitm; finish=timebuffer2.time; between_time2=difftime(finish,start); between_time2=between_time2*1000+finishm-startm;/ total2=total2+between_time2;printf(n快速排序的时间（以毫秒为单位）是：%6.6f,total1/1000);printf(n插入排序的时间（以毫秒为单位）是：%6.6f,total2/1000);betwee
8、n_time=total1/1000-total2/1000;printf(n两种排序相差的时间是：%6.6fnn,between_time);2用贪心算法实现背包问题，按下表格式列出其中的五种情况，其中物品个数、背包容量、物品重量和物品价值要随机产生。物品个数N背包容量C物品重量Wi物品价值Vi最优值最优解所需时间(ms)25.00002.0000 10.000026.0000 40.00002.0000 26.00003.0000 12.0000 38.00001.0000000038.333310.0000 3.0000 9.000021.0000 58.0000 58.00003.00
9、00 58.00005.3333 34.730492.37041.0000000049.00002.000010.00005.00007.0000 64.00002.00002.000096.00002.0000 64.00007.0000 96.0000160.00004.00000000510.66674.00009.00004.00008.00004.000076.000053.00006.000014.000072.00004.0000 76.00004.0000 72.00002.6667 15.7037163.70375.00000000613.66676.00004.00007.
10、00009.00005.00007.000042.000050.000066.000045.00007.000048.00004.0000 50.00007.0000 66.00002.6667 18.6667134.66675.00000000背包程序#include#include#include#includedouble W100;/重量double V100;/价值double unit_price100;/表示每个物品的单价void QuickSort(int low ,int high)/对单价进行排序long i,j;double x;double w,v;i=low;j=hi
11、gh;x=unit_pricei;w=Wi;v=Vi;while(i=x&ij) j-; unit_pricei=unit_pricej; Wi=Wj;/将重量，价值和单价的下标始终统一 Vi=Vj; while(unit_pricei=x&ij) i+; unit_pricej=unit_pricei; Wj=Wi; Vj=Vi; unit_pricei=x;Wi=w;Vi=v;if(low(j+1) QuickSort(j+1,high);void main()time_t start,finish;double between_time;int startm,finishm;struct
12、 _timeb timebuffer;int N,i,j;/N表示物品个数double sum=0,C,best_value=0;printf(n请输入物品个数(假设不超过100)：);scanf(%d,&N); /随机产生物品重量以及价值srand(unsigned)time(NULL);printf(n随机产生的物品重量,价值：);for(i=0;iN;i+) Wi=rand()%10+1;/重量产生的在10以内 Vi=rand()%100+1;/价值在100以内 printf(n%6.4lf , %6.4lf,Wi,Vi); for(i=0;iN;i+) sum=sum+Wi;C=sum/3+1;/将背包容量设为所有物品重量的三分之一加1printf(nn该背包的容量为：%6.4lf,C); /从此处开始计算时间_ftim
