课程设计--贪心算法

《课程设计--贪心算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计——贪心算法：任务调度问题数据结构课程设计贪心算法专业软件工程班级B软件121学号学生姓名1数据结构课程设计——贪心算法：任务调度问题目录1设计题目12设计分析13设计实现44测试方法74.1测试目的74.2测试输入74.3正确输出74.4实际输出75分析与探讨85.1测试结果分析85.2探讨与改进86设计小结81数据结构课程设计——贪心算法：任务调度问题1设计题目有n项任务，要求按顺序执行，并设定第i项任务需要t[i]单位时间。如果任务完成的顺序为1，2，…，n，那么第i项任务完成的时间为c[i]=t[1

2、]+…+t[i]，平均完成时间（AverageCompletionTime，ACT）即为（c[1]+…+c[n]）/n。本题要求找到最小的任务平均时间。输入要求：输入数据中包含几个测试案例。每一个案例的第一行给出一个不大于的整数n，接着下面一行开始列出n个非负整数t（t<=），每个数之间用空格相互隔开，以一个负数来结束输入。输出要求：对每一个测试案例，打印它的最小平均完成时间，并精确到0.01。每个案例对应的输出结果都占一行。若输入某一个案例中任务数目n=0，则对应输出一个空行。输入例子：44281-1表示有四个任务，各自

3、完成需要的时间单位分别是4，2，8，1，第三行输入-1表示结束。输出例子：要求程序运行后的输出结果为：6.50。2设计分析算法是为了求解一个问题需要遵循的，被青春地指定的简单指令的集合。任何程序基本上都是要用特点的算法来实现的。算法性能的好坏，直接决定了所实现程序性能的优劣。贪心算法通过一系列的选择来的得到一个问题的解。它所做的每一个选择都是当前的状态下某种意义的最好选择，即贪心选择。希望通过每次所做的贪心选择导致最终结果问题的一个最优解。这种启发式的策略并不总能奏效，然而在许多情况下能达到预期的目的。这个题目属于贪心算法

4、应用中的任务调度问题。要得到所有任务的平均完成时间，只需要将各个任务完成时间从小到大排序，任务实际完成需要的时间等于它等待的时间与自身执行需要的时间之和。这样给出的调度是按照最短作业优先进行来安排的。7数据结构课程设计——贪心算法：任务调度问题明确了可以用最短作业优先的思想后，就可以正式来设计题目的实现了。首先，输入的测试案例可以有很多组，每一个案例的输入格式都是第一行输入任务的个数，然后下面一行输入每一个任务需要的时间单位，输入完成另起一行，可以再继续输入下一个案例的数据。最后用一个任意的负数来表示输入的结束。这样，由于

5、案例的个数开始不得知，所以可以套用一个for循环。for(n=0;n>=0;)/*当n小于0的时候，退出程序*/{scanf(“%ld”,&n);if(n>0){建立一个具有n个元素的数组；for(i=0;i

6、排序的方法很多，如：冒泡排序、希尔排序、堆排序等，这些排序的方法都可以使用。这里采用希尔排序来实现，如图2.2所示。它的基本思想是：先取一个小于n的整数d1作为第一个增量；这里选取n的一半作为第一个增量（increment=n>>1），把数组的全部元素分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2

7、7数据结构课程设计——贪心算法：任务调度问题voidShellsort(long*a,longn){longi,j,increment;longtemp;/**第一个增量值为(n/2)，以后每一次的增量都是上一个增量值的一半**/for(increment=n>>1;increment>0;increment>>=1)/*每次的步长都是通过n值右移位来得到的*/{for(i=increment;i=increment;j-=i

8、ncrement){if(temp<*(a+(j-increment)))*(a+j)=*(a+(j-increment));elsebreak;}*(a+j)=temp;}}}（2）计算总的平均完成时间：排序完成后，数组a中的元素以升序的方式排序，因此总的平均完成时间为ACT＝∑(i=0,N)a[i]