课程设计报告-贪心算法：任务调度问题.doc

《课程设计报告-贪心算法：任务调度问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计报告贪心算法：任务调度问题的设计专业学生姓名班级学号指导教师完成日期目录1设计内容12）输入要求13）输出要求12设计分析12.1排序（将数组按照从小到大排序）的设计12.2多个测试案例的处理方法的设计22.3for循环设计22.4系统流程图23设计实践23.1希尔排序模块设计23.2多个测试案例的处理方法的模块设计34测试方法45程序运行效果46设计心得67附录6贪心算法：任务调度问题的设计1设计内容有n项任务，要求按顺序执行，并设定第I项任务需要t[i]单位时间。如果任务完成的顺序为

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

3、设计分析这个题目属于贪心算法应用中的任务调度问题。要得到所有任务的平均完成时间，只需要将各个任务完成时间从小到大排序，任务实际完成需要的时间等于它等待的时间与自身执行需要的时间之和。这样给出的调度是按照最短作业优先进行来安排的。贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。在许多可以用贪心算法求解的问题中一般具有两个重要的性质：贪心选择性质和最有子结构性质。所谓贪心选择性只是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到

4、，这是贪心算法可行的第一基本要素。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终将会得到问题的一个整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且做了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。当一个问题的最优解包含着它的子问题最优解时，称此问题具有最优子结构

5、性质，这个性质是该问题可用贪心算法求解的一个关键特征。2.1排序（将数组按照从小到大排序）的设计排序的方法有很多，如：冒泡排序、希尔排序、堆排序等，这些排序的方法都可以使用。这里采用希尔排序来实现。它的基本思想是：先取一个小于n的整数d1作为第一个增量；这里选取n的一半作为第一个增量（increment=n》1），把数组的全部元素分成d1个组。所有距离为d1的倍数的记录放在同一组中。先在各组内进行直接插入排序；然后，取第二个增量d2

6、·

7、数，然后下面一行输入每一个任务需要的时间单位，输入完成另起一行，可以再继续输入下一个案例的数据。最后用一个任意的负数来表示输入的结束。这样，由于案例的个数开始不得知，所以可以套用一个for循环。2.4系统流程图Main函数Menu==1Menu==0Case1输出排序之前结果排序sort()输出排序之后结果程序结束3设计实践3.1希尔排序模块设计voidShellsort(long*a,longn){longi,j,increment;longtemp;for(increment=n>>1;increm

8、ent>0;increment>>=1){for(i=increment;i=increment;j-=increment){if(temp<*(a+(j-increment)))*(a+j)=*(a+(j-increment));elsebreak;}*(a+j)=temp;}}}3.2多个测试案例的处理方法的模块设计doubler[100];/*用来存放每个测试案例的计算结果*