算法设计与分析学院：计算机科学与技术学号：*********姓名：***2014 11 141、 当问题规模100 N 时，快速排序和插入排序各需多少时间？写清机器配置，列出五种规模下各自需要的时间。

按照下列表格提交： 快速排序所需时间(ms) 插入排序所需时间（ms ） 两者相差多少 N=100 0.00600 0.019000 -0.013000 N=1000 0.074000 0.724000 -0.650000 N=10000 0.032000 64.657000 -64.625000 N=100000 13.300000 50.900000 -37.600000 N=100000053.500000117.700000-64.200000机器配置：Window 7 32位Cpu ：Inter(R)Core(TM)******************AMD Radeon HD 6450 Graphics程序：#include<stdio.h>#include<stdlib.h>#include<time.h>#include<sys\timeb.h> int a[1000000];int b[1000000];void QuickSort(int low ,int high){long i,j;int x;i=low;j=high;x=a[i];while(i<j){while(a[j]>=x&&i<j) j--;a[i]=a[j];while(a[i]<=x&&i<j) i++;a[j]=a[i];}a[i]=x;if(low<(i-1))QuickSort(low,i-1);if(high>(j+1))QuickSort(j+1,high);}void BinaryInsertSort(int length){int low,high,mid;int i,j,m;//m为保存待插入的元素for(i=1;i<length;i++){m=b[i];low=0;high=i-1;//设置初始区while(low<=high){mid=(low+high)/2;if(m>=b[mid])low=mid+1;elsehigh=mid-1;}for(j=i-1;j>=high+1;j--)//high为插入位置b[j+1]=b[j];//后移元素，留出插入的空位b[high+1]=m;//将元素插入正确的位置}}void main(){time_t start,finish;//time_t 相当于longdouble between_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;i<1000;i++){srand((unsigned)time(NULL));//对每次的排序进行设置随机种子（即编号）for(j=0;j<N;j++){a[j]=rand();b[j]=a[j];}//快速排序_ftime(&timebuffer1);//计算当前时间startm=litm;//start=timebuffer1.time;QuickSort(0,N-1);// printf("\n快速排序之后的数据为:");//for(i=0;i<N;i++)// {// printf("%d ",a[i]);// }_ftime(&timebuffer1);finishm=litm;finish=timebuffer1.time;between_time1=difftime(finish,start);//找出时间差between_time1=1000*between_time1+finishm-startm;total1=total1+between_time1;// 插入排序_ftime(&timebuffer2);startm=litm;start=timebuffer2.time;BinaryInsertSort(N);//printf("\n插入排序之后的数据为:");//for(i=0;i<N;i++)//{// printf("%d ",b[i]);// }_ftime(&timebuffer2);finishm=litm;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);between_time=total1/1000-total2/1000;printf("\n两种排序相差的时间是：%6.6f\n\n",between_time);}2用贪心算法实现背包问题，按下表格式列出其中的五种情况，其中物品个数、背包容量、物品重量和物品价值要随机产生。

4.0000 72.00006 13.6667 6.00004.00007.00009.00005.00007.0000 42.000050.000066.000045.00007.000048.00004.0000 50.00007.0000 66.00002.6667 18.6667134.6667 5.00000000背包程序#include<stdio.h>#include<stdlib.h>#include<time.h>#include<sys\timeb.h>double W[100];//重量double V[100];//价值double unit_price[100];//表示每个物品的单价void QuickSort(int low ,int high)//对单价进行排序{long i,j;double x;double w,v;i=low;j=high;x=unit_price[i];w=W[i];v=V[i];while(i<j){while(unit_price[j]>=x&&i<j) j--;{unit_price[i]=unit_price[j];W[i]=W[j];//将重量，价值和单价的下标始终统一V[i]=V[j];}while(unit_price[i]<=x&&i<j) i++;{unit_price[j]=unit_price[i];W[j]=W[i];V[j]=V[i];}}unit_price[i]=x;W[i]=w;V[i]=v;if(low<(i-1))QuickSort(low,i-1);if(high>(j+1))QuickSort(j+1,high);}void main(){time_t start,finish;double between_time;int startm,finishm;struct _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;i<N;i++){W[i]=rand()%10+1;//重量产生的在10以内V[i]=rand()%100+1;//价值在100以内printf("\n%6.4lf , %6.4lf",W[i],V[i]);}for(i=0;i<N;i++)sum=sum+W[i];C=sum/3+1;//将背包容量设为所有物品重量的三分之一加1 printf("\n\n该背包的容量为：%6.4lf",C);//从此处开始计算时间_ftime(&timebuffer);startm=litm;start=timebuffer.time;for(i=0;i<N;i++)unit_price[i]=V[i]/W[i];QuickSort(0,N-1);//对单价进行排序(升序)for(i=N-1;i>=0;i--){if(C<=W[i])break;elseC=C-W[i];}printf("\n\n最优解如下：");printf("\n物品重量物品价值");for(j=N-1;j>i;j--){printf("\n%6.4lf %6.4lf",W[j],V[j]);best_value=best_value+V[j];}printf("\n%6.4lf %6.4lf",C,C*unit_price[i]);best_value=best_value+C*unit_price[i];printf("\n\n最优值为：%6.4lf",best_value);//计算时间结束_ftime(&timebuffer);finishm=litm;finish=timebuffer.time;between_time=difftime(finish,start)*1000+finishm-startm;printf("\n\n该次所需时间为：%6.8lf\n\n",between_time);}3趣味矩阵：#include<stdio.h>main(){char a[100][100];int i,j,n;scanf("%d",&n);for(i=1;i<=n;i++)for(j=1;j<=n;j++){if((i==j)||(i+j==n+1)) a[i][j]='A';else if(i<j&&i+j<n+1) a[i][j]='B';else if(i>j&&i+j<n+1) a[i][j]='C';else if(i>j&&i+j>n+1) a[i][j]='D';else a[i][j]=4;}for(i=1;i<=n;i++){for(j=1;j<=n;j++)printf("%c ",a[i][j]);printf("\n");}}4 请仔细阅读题目描述、你的任务及提示信息题目描述：某校的惯例是在每学期的期末考试之后发放奖学金。