课程设计--贪心算法.doc

数据结构课程设计贪心算法：任务调度问题数据结构课程设计贪心算法专业软件工程班级B软件121学号1210701132学生姓名 1目 录1 设计题目12 设计分析13 设计实现44测试方法74.1测试目的74.2 测试输入74.3 正确输出74.4 实际输出75 分析与探讨85.1 测试结果分析85.2 探讨与改进86 设计小结8 11 设计题目 有n项任务，要求按顺序执行，并设定第i项任务需要ti单位时间。如果任务完成的顺序为1，2，n，那么第i项任务完成的时间为ci=t1+ti，平均完成时间（Average Completion Time，ACT）即为（c1+cn）/n。本题要求找到最小的任务平均时间。输入要求：输入数据中包含几个测试案例。每一个案例的第一行给出一个不大于2000000的整数n，接着下面一行开始列出n个非负整数t（t=0;) /*当n小于0的时候，退出程序*/ scanf(“%ld”,&n); if(n0) 建立一个具有n个元素的数组； for(i=0;i1），把数组的全部元素分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量dt=1（dtd(t-1)d21; increment0; increment=1 ) /*每次的步长都是通过n值右移位来得到的*/ for(i = increment; i =increment; j-= increment) if( temp *(a + (j-increment) ) *(a+j)= *( a+ (j-increment) ); else break; *(a+j) = temp; （2）计算总的平均完成时间：排序完成后，数组a中的元素以升序的方式排序，因此总的平均完成时间为ACT(i=0,N)ai*(n-i)/n（3）输出调度结果：由于输出的结果要求精确到0.01，所以输出的时候需要采用以下输出格式。double r100; /*依次存放每个案例的ACT*/printf(“%.2fn”,ri);/*输出的结果要求精确到0.01*/另外，程序实现的时候，要求用户一次可以输入一组或者多组测试案例的数据，当用户的输入完成后，程序经过计算在屏幕上分行显示这几个案例的结果。因此，在有多个测试案例的情况下，需要设置一个数组，用来存放每一组测试案例的计算结果。double r100; /*用来存放每个测试案例的计算结果*/j=0; /*记录测试案例的个数*/for(对每一个测试案例)把计算得到的最优调度时间放入rj中；j+;/*当输入的n值为负数时。跳出上面的for循环*/for(从0到j) if(ri=-1)printf(n);/*输出一个空行*/ else printf( %.2fn, ri );/*输出的结果要求精确到0.01*/ 3 设计实现#include #include /* run this program using the console pauser or add your own getch, system(pause) or input loop */void Shellsort( long *a, long n );int main() long n,i,j; long *a,*b;double r100;/* 用来存放每个测试案例的计算结果 */j=0;/* 记录测试案例的个数 */*读入用户的输入，若当前输入为负数，则程序终止*/ for( n = 0; n = 0 ; ) scanf( %ld, &n );if(n 2000000)printf(too much for the project!n);exit(0); if( n 0 ) b = (long*)malloc( n * sizeof( long ) ); a = b; for(i=0; i 1000000000)printf(too much for the project!n);exit(0); /* 对输入中出现任务时间为负数的异常处理 */ if(*(b+i) 0 ; i-,a+ ) rj+= (double)*a/(double)n * i; j+; free( b ); /* 当n为0时，标志相应的r数组值为1，输出时碰到1则输出一个空行*/ else if ( n = 0 ) rj+=-1; for(i=0;i1; increment0; increment=1 ) for(i = increment; i =increment; j-= increment) if( temp *(a + (j-increment) ) *(a+j)= *( a+ (j-increment) ); else break; *(a+j) = temp; 4测试方法4.1测试目的检验程序是否正常运行并完成算法的要求。4.2 测试输入44 1 2 352 3 4 1 5-14.3 正确输出5.007.004.4 实际输出 5 分析与探讨5.1 测试结果分析 调试与运行过程中，程序可以正常运行，并在输入不同数据情况下分别给出正确的结果，说明该程序正确无误，完成了此次课程设计题目的要求。5.2 探讨与改进总的来说，该程序已基本实现了贪心算法的要求功能，但还可以对其中的一些细节进行优化，比如程序的运行结果界面可以加上更多的文字描述与提示，增加观赏性，也可以用起来更方便。 6 设计小结在本次为期一周的数据结构课程设计中，我的题目是贪心算法：任务调度问题，贪心算法采用的是逐步构造最优解的方法，类似的任务调度问题在生活有很多，虽然有时候我们都没感觉到它的存在，但不能否认有时候我们不经意间已经使用了贪心算法去寻找最优解的方法。这个是我对这个题目最基本的认识，也增加了自己在以后生活中的经验。从数据结构这门课的角度，虽然书中给了源代码供我们参考，但在通过自己去调试，成功的运行这个程序的过程中，还是会遇到一些问题，通过自己查阅书上的内容，向同学请教，最终得以圆满解决，这也让自己学到很多，用的有C语言的知识，还有数据结构这门课本身，不仅巩固以前的知识，加深了认识，还得到了很多实践的过程中带给自己的收获。在本次课程设计中，面对很多问题也发现了自己的不足之处还很多，很多知识不牢固，不明晰，不能熟练的