算法分析与设计实验报告.pdf
算法设计与分析 学院：计算机科学与技术 学号：*姓名：*2014 11 14 1、当问题规模100N时，快速排序和插入排序各需多少时间？写清机器配置，列出五种规模下各自需要的时间。按照下列表格提交：快速排序所需时间(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=1000000 53.500000 117.700000-64.200000 机器配置：Window 7 32 位 Cpu：Inter(R)Core(TM)*AMD Radeon HD 6450 Graphics 程序：#include#include#include#include int 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);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;else high=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 相当于 long double 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;i1000;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.millitm;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+)/printf(%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);between_time=total1/1000-total2/1000;printf(n 两种排序相差的时间是：%6.6fnn,between_time);2 用贪心算法实现背包问题，按下表格式列出其中的五种情况，其中物品个数、背包容量、物品重量和物品价值要随机产生。物品个数N 背包容量C 物品重量Wi 物品价值Vi 最优值 最优解 所 需 时 间(ms)2 5.0000 2.0000 10.0000 26.0000 40.0000 2.0000 26.0000 3.0000 12.0000 38.0000 1.00000000 3 8.3333 10.0000 3.0000 9.0000 21.0000 58.0000 58.0000 3.0000 58.0000 5.3333 34.7304 92.3704 1.00000000 4 9.0000 2.0000 10.0000 5.0000 7.0000 64.0000 2.0000 2.0000 96.0000 2.0000 64.0000 7.0000 96.0000 160.0000 4.00000000 5 10.6667 4.0000 9.0000 4.0000 8.0000 76.0000 53.0000 6.0000 14.0000 4.0000 76.0000 4.0000 72.0000 2.6667 15.7037 163.7037 5.00000000 4.0000 72.0000 6 13.6667 6.0000 4.0000 7.0000 9.0000 5.0000 7.0000 42.0000 50.0000 66.0000 45.0000 7.0000 48.0000 4.0000 50.0000 7.0000 66.0000 2.6667 18.6667 134.6667 5.00000000 背包程序#include#include#include#include double W100;/重量 double V100;/价值 double unit_price100;/表示每个物品的单价 void QuickSort(int low,int high)/对单价进行排序 long i,j;double x;double w,v;i=low;j=high;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 _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;/将背包容量设为所有物品重量的三分之一加 1 printf(nn 该背包的容量为：%6.4lf,C);/从此处开始计算时间 _ftime(&timebuffer);startm=timebuffer.millitm;start=timebuffer.time;for(i=0;i=0;i-)if(Ci;j-)printf(n%6.4lf%6.4lf,Wj,Vj);best_value=best_value+Vj;printf(n%6.4lf%6.4lf,C,C*unit_pricei);best_value=best_value+C*unit_pricei;printf(nn 最优值为：%6.4lf,best_value);/计算时间结束 _ftime(&timebuffer);finishm=timebuffer.millitm;finish=timebuffer.time;between_time=difftime(finish,start)*1000+finishm-startm;printf(nn 该次所需时间为：%6.8lfnn,between_time);3趣味矩阵：#include main()char a100100;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)aij=A;else if(ij&i+jj&i+jj&i+jn+1)aij=D;else aij=4;for(i=1;i=n;i+)for(j=1;j80），并且在本学期内发表1 篇或 1 篇以上论文的学生均可获得；2)五四奖学金，每人 4000 元，期末平均成绩高于 85 分（85），并且班级评议成绩高于 80 分（80）的学生均可获得；3)成绩优秀奖，每人 2000 元，期末平均成绩高于 90 分（90）的学生均可获得；4)西部奖学金，每人 1000 元，期末平均成绩高于 85 分（85）的西部省份学生均可获得；5)班级贡献奖，每人 850 元，班级评议成绩高于 80 分（80）的学生干部均可获得；只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是 87 分，班级评议成绩 82 分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是 4850 元。你的任务:现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。并给出实现代码和 5 组实验数据。输入格式：输入的第一行是一个整数 N（1=N=100），表示学生的总数。接下来的 N 行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过 20的字符串（不含空格）；期末平均成绩和班级评议成绩都是 0 到 100 之间的整数（包括 0和 100）；是否是学生干部和是否是西部省份学生分别用一个字符表示，Y 表示是，N 表示不是；发表的论文数是 0 到 10 的整数（包括 0 和 10）。每两个相邻数据项之间用一个空格分隔。输出格式：输出包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。第三行是这 N 个学生获得的奖学金的总数。样例输入：4 YaoLin 87 82 Y N 0 ChenRuiyi 88 78 N Y 1 LiXin 92 88 N N 0 ZhangQin 83 87 Y N 1 样例输出：ChenRuiyi 9000 28700 程序：#include using namespace std;int main()int i,j,n,qm,py,lw,prize,max=0;long total=0;char a20,name20,xb,gb;cinn;for(i=1;iaqmpygbxblw;prize=0;if(qm80)&(lw0)prize+=8000;if(qm85)&(py80)prize+=4000;if(qm90)prize+=2000;if(qm85)&(xb=Y)prize+=1000;if(py80)&(gb=Y)prize+=850;total+=prize;if(prizemax)max=prize;for(j=0;j20;j+)namej=aj;coutnameendlmaxendltotal;return 0;
