算法设计实验报告.doc

算法设计与分析实验报告 指导老师：王喜凤学号：089074106姓名：曹连娇班级：计084班实验一:题目：当问题规模时，快速排序和插入排序各需多少时间（100次平均结果）？写清机器配置，列出五种规模下各自需要的时间。按照下列表格提交：快速排序所需时间(ms)插入排序间（ms）两者相差多少N=1000.0000.0000N=10000,0141.8701.756N=100001.800122.740120.94N=10000023.50014786.35414762.854N=1000000302.000运行环境：运用Visual C+ 6.0编写和执行程序#define N 10000#include#include using namespace std;void q_sort(int a,long low,long 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(lowi-1) q_sort(a,low,i-1); if(j+1high) q_sort(a,j+1,high);void i_sort(int b)long i,j;int x;for(i=1;iN;i+)x=bi;j=i-1;while(xbj)bj+1=bj;j-;bj+1=x;int main()int aN,bN;int j;long i;double qq=0,ii=0;for(j=0;j100;j+)srand(unsigned)time(NULL);for(i=0;iN;i+)ai=rand();bi=ai;clock_t q_start,q_end;clock_t i_start,i_end;double q_time,i_time;i_start=clock();i_sort(b);i_end=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,N,qq/100);printf(%ld个随机数进行插入排序用时%6.0f毫秒n,N,ii/100);return 0;实验二：下表格式列出其中的五种情况，其中物品个数、背包容量、物品重量和物品价值要随机产生。物品个数N背包容量C物品重量Wi物品价值V最优值最优解所需时间(ms)28（5，10）（1，5）4（0，08）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 #include #includetime.h struct goodinfo float v; /物品的效益 float w; /物品的重量 float X; int flag; ;/物品信息结构体 void Insertionsort(goodinfo goods,int n) /插入排序，按vi/wi价值收益进行排序 int j,i; for(j=2;jgoodsi.v) goodsi+1=goodsi; i-; goodsi+1=goods0; /按物品效益，重量比值做升序排列 void bag(goodinfo goods,float M,int n) float cu; int i,j; for(i=1;i=n;i+) goodsi.X=0; cu=M; /背包剩余容量 for(i=1;icu)/当该物品重量大与剩余容量跳出 break; goodsi.X=1; cu=cu-goodsi.w;/确定背包新的剩余容量 if(i=n) goodsi.X=cu/goodsi.w;/该物品所要放的量 /*按物品编号做降序排列*/ for(j=2;j=n;j+) goods0=goodsj; i=j-1; while (goods0.flaggoodsi.flag) goodsi+1=goodsi; i-; goodsi+1=goods0; cout最优解为:endl; for(i=1;i=n;i+) cout第i件物品要放:; coutgoodsi.Xendl; void main() clock_t start,end; double ltime; start=clock(); cout|-运用贪心法解背包问题-|endl; int j,n, M; goodinfo *goods;/定义一个指针 while(j) coutn; coutn;coutendl; goods=new struct goodinfo n+1;/ cout背包的最大容量：; M=(float)(rand()%20+1); coutM; coutendl; int i; for(i=1;i=n;i+) goodsi.flag=i; cout第i件物品的重量:; float a=(float)(rand()%10+1); goodsi.w=a; cout a ; coutendl; cout第i件物品的效益:; float b=(float)(rand()%10+1); goodsi.v=b; cout b ;coutendl; goodsi.v=goodsi.v/goodsi.w;/得出物品的效益，重量比 coutendl; Insertionso