正宗清炖牛肉的做法课程设计--贪心算法

2021年1月17日发(作者：伍先华)

课程设计
--
贪心算法










数
据
结
构
课
程
设
计



贪心算法

















数据结构课程设计——贪心算法：任务调度问题


专
班
学
业

级

号

软件工程

B
软件
121
1210701132


学生姓名




2
数据结构课程设计——贪心算法：任务调度问题


目

录








4.4
实际输出
............................. .................................................. ........................... 8

5

分析与探讨
.................................... .................................................. ...................... 8

5.1
测试结果分析
................................... .................................................. ............. 8

5.2
探讨与改进
........ .................................................. ............................................ 8

6

设计小结
............................ .................................................. ................................... 8

1

设计题目
........................... .................................................. ..................................... 1
2
< br>设计分析
....................................... .................................................. ........................ 1
3

设计实现
.. .................................................. .................................................. ........... 4
4
测试方法
................... .................................................. ............................................ 7
4.1
测试目的
............................. .................................................. ............................ 7
4.2
测试输入
.................................................. .................................................. ...... 7
4.3
正确输出
..................... .................................................. ................................... 7


数据结构课程设计——贪心算法：任务调度问题

1
设计题目

有
n
项任务，要求按顺序执行，并设定第
i
项任务需要
t[ i]
单位时间。如果任务
完成的顺序为
1
，
2
，…，
n
，那么第
i
项任务完成的时间为
c[i]=t[1]+
…
+t[i]
，平
均完成时间（
Average
Completion < br>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
设计分析

算法是为了求解一个问题需要遵循的，被青春地指定的简单指令的集合。任 何
程序基本上都是要用特点的算法来实现的。算法性能的好坏，直接决定了所实现程
序性能的优 劣。贪心算法通过一系列的选择来的得到一个问题的解。
它所做的每一
个选择都是当前的状态下 某种意义的最好选择，即贪心选择。
希望通过每次所做的
贪心选择导致最终结果问题的一个最优 解。这种启发式的策略并不总能奏效，
然而
在许多情况下能达到预期的目的。

这个题目属于贪心算法应用中的任务调度问题。
要得到所有任务的平均完成时
间，只需要将各 个任务完成时间从小到大排序，任务实际完成需要的时间等于它等
待的时间与自身执行需要的时间之和。
这样给出的调度是按照最短作业优先进行来
安排的。

明确了可以用最短作业优先的思想后，就可以正式来设计题目的实现了。首先，输

1
数据结构课程设计——贪心算法：任务调度问题

入的测试案例可以有很多组，每一个 案例的输入格式都是第一行输入任务的个数，
然后下面一行输入每一个任务需要的时间单位，输入完成另 起一行，
可以再继续输
入下一个案例的数据。最后用一个任意的负数来表示输入的结束。这样， 由于案例
的个数开始不得知，所以可以套用一个
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
的一半
作为第一个增量（
in crement=n>>1
），把数组的全部元素分成
d1
个组。所有距离为
d1
的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个
增量
d2重复上述的分组和排序，直至所取的增量
dt=1
（
dt…
），
即所有记录放在同一组中进行直接插入排序为 止。
该方法实质上是一种分组插入排
序方法。


2