实用标准文案精彩文档数据结构课程设计报告贪心算法：任务调度问题的设计专业学生姓名班级学号指导教师完成日期实用标准文案精彩文档目录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]单位时间。如果任务完成的顺序为1，2，⋯，n，那么第I项任务完成的时间为c[i]=t[1]+⋯+t[i]，平均完成时间（ACT）即为（c[1]+..+c[n]）/n。本题要求找到最小的任务平均完成时间。2）输入要求输入数据中包含n个测试案例。每一个案例的第一行给出一个不大于2000000的整数n，接着下面一行开始列出n各非负整数t（t≤1000000000），每个数之间用空格相互隔开，以一个负数来结束输入。3）输出要求对每一个测试案例，打印它的最小平均完成时间，并精确到0.01。每个案例对应的输出结果都占一行。若输入某一个案例中任务数目n=0，则对应输出一个空行。2设计分析这个题目属于贪心算法应用中的任务调度问题。要得到所有任务的平均完成时间，只需要将各个任务完成时间从小到大排序，任务实际完成需要的时间等于它等待的时间与自身执行需要的时间之和。这样给出的调度是按照最短作业优先进行来安排的。贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。在许多可以用贪心算法求解的问题中一般具有两个重要的性质：贪心选择性质和最有子结构性质。所谓贪心选择性只是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，这是贪心算法可行的第一基本要素。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终将会得到问题的一个整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且做了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。当一个问题的最优解包含着它的子问题最优解时，称此问题具有最优子结构性质，这个性质是该问题可用贪心算法求解的一个关键特征。2.1排序（将数组按照从小到大排序）的设计排序的方法有很多，如：冒泡排序、希尔排序、堆排序等，这些排序的方法都可以使用。这里采用希尔排序来实现。它的基本思想是：先取一个小于n的整数d1作为第一个增量；这里选取n的一半作为第一个增量（increment=n》1），把数组的全部元素分成d1个组。所有距实用标准文案精彩文档离为d1的倍数的记录放在同一组中。先在各组内进行直接插入排序；然后，取第二个增量d2
