鲅鱼怎么读课程设计报告-贪心算法：任务调度问题

2021年1月17日发(作者：许征帆)











数
据
结
构
课
程
设
计
报
告

贪心算法：任务调度问题的设计

















专
业







学生姓名

班
学
级

号

指导教师

完成日期




贪心算法：任务调度问题的设计

目

录

1

设计内容

.
.................. .................................................. .............................................. 1

2
）输入要求
......................... .................................................. ................................... 1

3
）输出要求
............................... .................................................. ............................. 1

2

设计分析

.
............................ .................................................. .................................. 1

2.1

排序（将数组按照从小到大排序）的设计
........... .......................................... 1

2.2

多个测试案例的处理方法的设计
............... .................................................. .... 2

2.3 for
循环设计
................ .................................................. ....................................... 2

2.4
系统流程图
............................. .................................................. ........................... 2

3
设计实践
................................ .................................................. ............................... 2

3.1
希尔排序模块设计
.......................... .................................................. .................. 2

3.2
多个测试案例的处理方法的模块设计
......................... .................................... 3

4
测试方法
................................ .................................................. ............................... 4

5

程序运行效果

.
.......................... .................................................. ............................ 4

6

设计心得

.
............................ .................................................. .................................. 6

7
附录
.................................. .................................................. ..................................... 6



数据结构课程设计报告（
2017
）

贪心算法：任务调度问题的设计

1

设计内容

有
n
项任务，要求按顺序执行，并设定第
I
项任务需要
t[i]< br>单位时间。如果任
务完成的顺序为
1
，
2
，…，
n< br>，那么第
I
项任务完成的时间为
c[i]=t[1]+
…
+t [i]
，
平均完成时间（
ACT
）即为（
c[1]+..+c[n]
）
/n
。本题要求找到最小的任务平均完
成时间。

2
）输入要求

输入数据中包含
n
个测试案例。每一个案例 的第一行给出一个不大于
2000000
的整数
n
，接着下面一行开始列出< br>n
各非负整数
t
（
t
≤
1000000000
）
，每个数之间
用空格相互隔开，以一个负数来结束输入。

3
）输出要求

对每一个测试案例，打印它的最小平均完成时间，并精确到< br>0.01
。每个案例对
应的输出结果都占一行。
若输入某一个案例中任务数目< br>n=0
，
则对应输出一个空行。

2
设计分析






这个题目属于贪心算法应用中的任务调度问题。
要得到所有任务的平均完成时
间，只需要将各个任务完成时间从小到大排序，任务实际完成需要 的时间等于它等
待的时间与自身执行需要的时间之和。这样给出的调度是按照最短作业优先进行来
安排的。贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都
是当前状态下某种意 义的最好选择，即贪心选择。在许多可以用贪心算法求解的问
题中一般具有两个重要的性质：贪心选择性 质和最有子结构性质。所谓贪心选择性
只是指所求问题的整体最优解可以通过一系列局部最优的选择，即 贪心选择来达
到，这是贪心算法可行的第一基本要素。对于一个具体问题，要确定它是否具有贪
心选择性质，必须证明每一步所做的贪心选择最终将会得到问题的一个整体最优
解。首先考察问题的一个 整体最优解，并证明可修改这个最优解，使其以贪心选择
开始。而且做了贪心选择后，原问题简化为一个 规模更小的类似子问题。然后，用
数学归纳法证明，通过每一步做贪心选择，最终可得到问题的一个整体 最优解。其
中，证明贪心选择后问题简化为规模更小的类似子问题的关键在于利用该问题的最
优 子结构性质。当一个问题的最优解包含着它的子问题最优解时，称此问题具有最
优子结构性质，这个性质 是该问题可用贪心算法求解的一个关键特征。

2.1

排序（将数组按照从小到大排序）的设计






排序的方法有很多，如：冒泡排序、希尔排序、堆排序等，这些排序的方法都
可以使 用。这里采用希尔排序来实现。


它的基本思想是：先取一个小于
n
的整数
d1
作为第一个增量；这里选取
n
的
一半作为第一 个增量（
increment=n
》
1
）
，把数组的全部元素分成< br>d1
个组。所有距

1
贪心算法：任务调度问题的设计
< br>离为
d1
的倍数的记录放在同一组中。先在各组内进行直接插入排序；然后，取第
二
个
增
量
d2重
复
上
述
的
分
组
和
排
序
，
直
至
所
取
的
增
量
d1=1
（
dt·
·
·
）
，即所有记录放在同一组中进行直接插入排序位置。该方
法实质上是一种分组插入排序方法。


2.2

多个测试案例的处理方法的设计








程序实现的时候，要求用户一次可以输入椅子或者多组测试案例的数据，当
要迷糊糊的输入完成后，程序经过计算在屏幕上分行显示这几个案例的结果。因此
有多个测试案例的情 况下，需要设置一个数组，用来存放么每一组测试案例的计算
结果。

2.3 for
循环设计

明确了可以用最短作业优先的思想后，就可以正式来设计题目的实现 了。首先，输
入的测试案例可以有很多组，每一个案例的输入格式都是第一行输入任务的个数，
然后下面一行输入每一个任务需要的时间单位，输入完成另起一行，可以再继续输
入下一个案例的数据。 最后用一个任意的负数来表示输入的结束。这样，由于案例
的个数开始不得知，所以可以套用一个
for
循环。

2.4
系统流程图




















Main
函数

Menu==0
Menu==1
程序结束

Case 1

输出排
序之前结果排序
sort()

输出排序
之后结果


3
设计实践

3.1
希尔排序模块设计

void Shellsort(long *a,long n)
{

long i,j,increment;

long temp;

for(increment=n>>1;increment>0;increment>>=1)

{


for(i=increment;i
2