课程设计--贪心算法
课程设计--贪心算法
数据结构课程设计
贪心算法
专业软件工程班级B软件121 学号1210701132 学生姓名
目录
1设计题目 (1)
2设计分析 (1)
3设计实现 (4)
4测试方法 (7)
4.1测试目的 (7)
4.2 测试输入 (7)
4.3 正确输出 (7)
4.4 实际输出 (8)
5分析与探讨 (8)
5.1 测试结果分析 (8)
5.2 探讨与改进 (8)
6设计小结 (8)
1 设计题目
有n项任务，要求按顺序执行，并设定第i项任务需要t[i]单位时间。如果任务完成的顺序为1，2，…，n，那么第i项任务完成的时间为c[i]=t[1]+…+t[i]，平均完成时间（Average Completion Time，ACT）即为（c[1]+…+c[n]）/n。本题要求找到最小的任务平均时间。
输入要求：
输入数据中包含几个测试案例。每一个案例的第一行给出一个不大于2000000的整数n，接着下面一行开始列出n个非负整数t（t<=1000000000），每个数之间用空格相互隔开，以一个负数来结束输入。
输出要求：
对每一个测试案例，打印它的最小平均完成时间，并精确到0.01。每个案例对应的输出结果都占一行。若输入某一个案例中任务数目n=0，则对应输出一个空行。
输入例子：
4
4 2 8 1
-1
表示有四个任务，各自完成需要的时间单位分别是4，2，8，1，第三行输入-1表示结束。
输出例子：
要求程序运行后的输出结果为：6.50。
2 设计分析
算法是为了求解一个问题需要遵循的，被青春地指定的简单指令的集合。任何程序基本上都是要用特点的算法来实现的。算法性能的好坏，直接决定了所实现程序性能的优劣。贪心算法通过一系列的选择来的得到一个问题的解。它所做的每一个选择都是当前的状态下某种意义的最好选择，即贪心选择。希望通过每次所做的贪心选择导致最终结果问题的一个最优解。这种启发式的策略并不总能奏效，然而在许多情况下能达到预期的目的。
这个题目属于贪心算法应用中的任务调度问题。要得到所有任务的平均完成时间，只需要将各个任务完成时间从小到大排序，任务实际完成需要的时间等于它等待的时间与自身执行需要的时间之和。这样给出的调度是按照最短作业优先进行来安排的。
明确了可以用最短作业优先的思想后，就可以正式来设计题目的实现了。首先，输
入的测试案例可以有很多组，每一个案例的输入格式都是第一行输入任务的个数，然后下面一行输入每一个任务需要的时间单位，输入完成另起一行，可以再继续输入下一个案例的数据。最后用一个任意的负数来表示输入的结束。这样，由于案例的个数开始不得知，所以可以套用一个for循环。
for(n=0;n>=0;) /*当n小于0的时候，退出程序*/
{
scanf(“%ld”,&n);
if(n>0)
{
建立一个具有n个元素的数组；
for(i=0;i { 继续读入这n个作业的完成时间； } 进行主要的调度运算； 输出得到的最优调度结果； } else if(n==0) { 输出一个空行； } } 所以，对每组输入，其基本过程是：读入n个任务的运行时间，进行主要的调度运算。已经明确了采用最短作业优先的程序思想，所以主要的调度运算包括3个步骤： (1)排序：将数组按照从小到大排序。 排序的方法很多，如：冒泡排序、希尔排序、堆排序等，这些排序的方法都可以使用。这里采用希尔排序来实现，如图2.2所示。 它的基本思想是：先取一个小于n的整数d1作为第一个增量；这里选取n的一半作为第一个增量（increment=n>>1），把数组的全部元素分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 void Shellsort( long *a, long n ) { long i, j, increment; long temp; /** 第一个增量值为(n/2)，以后每一次的增量都是上一个增量值的一半**/ for( increment = n>>1; increment>0; increment>>=1 ) /*每次的步长都是通过n值右移位来得到的*/ { for(i = increment; i < n; i++) { /*对每一组里面的元素进行插入排序*/ temp = *(a+i); for(j = i; j>=increment; j-= increment) { if( temp < *(a + (j-increment)) ) *(a+j)= *( a+ (j-increment) ); else break; } *(a+j) = temp; } } } （2）计算总的平均完成时间：排序完成后，数组a中的元素以升序的方式排序，因此总的平均完成时间为 ACT＝∑(i=0,N)a[i]*(n-i)/n （3）输出调度结果：由于输出的结果要求精确到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 r[100];/**** 用来存放每个测试案例的计算结果***/ 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< n ; i++) { scanf( "%ld", b+i ); /*** 检查输入的数据是否大于1000 000 000****/ if(*(b+i) > 1000000000){ printf("too much for the project!\n"); exit(0); } /*** 对输入中出现任务时间为负数的异常处理******/ if(*(b+i)<0) { printf("input error！\n"); return 0; } } Shellsort( b, n ); /***** 计算平均完成时间*****/ for( i = n, r[j] = 0.0; i > 0 ; i--,a++ ) { r[j]+= (double)*a/(double)n * i; } j++; free( b ); } /*** 当n为0时，标志相应的r数组值为－1，输出时碰到－1则输出一个空行***/ else if ( n == 0 ) { r[j++]=-1; } } for(i=0;i { if(r[i]==-1)printf("\n");/** 输出一个空行**/ else printf( "%.2f\n", r[i] );/** 输出的结果要求精确到0.01 **/ } return 1; } /*** 希尔排序方法***/ void Shellsort( long *a, long n ) { long i, j, increment; long temp; /** 第一个增量值为(n/2)，以后每一次的增量都是上一个增量值的一半**/ for( increment = n>>1; increment>0; increment>>=1 ) { for(i = increment; i < n; i++) { temp = *(a+i); for(j = i; j>=increment; j-= increment) { if( temp < *(a + (j-increment)) ) *(a+j)= *( a+ (j-increment) ); else break; } *(a+j) = temp; } } } 4测试方法 4.1测试目的 检验程序是否正常运行并完成算法的要求。 4.2 测试输入 4 4 1 2 3 5 2 3 4 1 5 -1 4.3 正确输出 5.00 7.00 4.4 实际输出 5 分析与探讨 5.1 测试结果分析 调试与运行过程中，程序可以正常运行，并在输入不同数据情况下分别给出正确的结果，说明该程序正确无误，完成了此次课程设计题目的要求。 5.2 探讨与改进 总的来说，该程序已基本实现了贪心算法的要求功能，但还可以对其中的一些细节进行优化，比如程序的运行结果界面可以加上更多的文字描述与提示，增加观赏性，也可以用起来更方便。 6 设计小结 在本次为期一周的数据结构课程设计中，我的题目是贪心算法：任务调度问题，贪心算法采用的是逐步构造最优解的方法，类似的任务调度问题在生活有很多，虽然有时候我们都没感觉到它的存在，但不能否认有时候我们不经意间已经使用了贪心算法去寻找最优解的方法。这个是我对这个题目最基本的认识，也增加了自己在以后生活中的经验。从数据结构这门课的角度，虽然书中给了源代码供我们参考，但在通过自己去调试，成功的运行这个程序的过程中，还是会遇到一些问题，通过自己查阅书上的内容，向同学请教，最终得以圆满解决，这也让自己学到很多，用的有C语言的知识，还有数据结构这门课本身，不仅巩固以前的知识，加深了认识， 还得到了很多实践的过程中带给自己的收获。 在本次课程设计中，面对很多问题也发现了自己的不足之处还很多，很多知识不牢固，不明晰，不能熟练的运用，这需要自己以后在学习过程中不断的深化改进。当然，我也认识到了理论和实践相结合的重要性，课本上的知识是不够的，只有自己多操作，多练习，才能得到更多的收获，才能提高自己的动手能力和独立思考的能力。只有不断的结合理论与实践才能真正提高自己的能力，才能让课本上的知识得到升华。