数据结构课程设计

贪心算法。

目录。1 设计题目 1

2 设计分析 1

3 设计实现 1

4测试方法 4

4.1测试目的 7

4.2 测试输入 7

4.3 正确输出 7

4.4 实际输出 7

5 分析与** 7

5.1 测试结果分析 7

5.2 **与改进 8

6 设计小结 8

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

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

输出要求：对每一个测试案例，打印它的最小平均完成时间，并精确到0.01。

每个案例对应的输出结果都占一行。若输入某一个案例中任务数目n=0，则对应输出一个空行。输入例子：

表示有四个任务，各自完成需要的时间单位分别是4，2，8，1，第三行输入-1表示结束。

输出例子：要求程序运行后的输出结果为：6.50。

算法是为了求解一个问题需要遵循的，被青春地指定的简单指令的集合。任何程序基本上都是要用特点的算法来实现的。算法性能的好坏，直接决定了所实现程序性能的优劣。

贪心算法通过一系列的选择来的得到一个问题的解。它所做的每一个选择都是当前的状态下某种意义的最好选择，即贪心选择。希望通过每次所做的贪心选择导致最终结果问题的一个最优解。

这种启发式的策略并不总能奏效，然而在许多情况下能达到预期的目的。

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

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

这样，由于案例的个数开始不得知，所以可以套用一个for循环，如图2.1所示。

for(n=0;n>=0;) 当n小于0的时候，退出程序*/

scanf(“%ld”,&n);

if(n>0)

else if(n==0)

图2.1 采用的for循环。

所以，对每组输入，其基本过程是：读入n个任务的运行时间，进行主要的调度运算。已经明确了采用最短作业优先的程序思想，所以主要的调度运算包括3个步骤：

1)排序：将数组按照从小到大排序。

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

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

先在各组内进行直接插入排序；然后，取第二个增量d2void shellsort( long *a, long n )

long i, j, increment;

long temp;

** 第一个增量值为(n/2)，以后每一次的增量都是上一个增量值的一半 **

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

/*每次的步长都是通过n值右移位来得到的*/

图2.2 希尔排序的实现。

2）计算总的平均完成时间：排序完成后，数组a中的元素以升序的方式排序，因此总的平均完成时间为。

act＝∑(i=0,n)a[i]*(n-i)/n

3）输出调度结果：由于输出的结果要求精确到0.01，所以输出的时候需要采用以下输出格式。

图2.3 要求输出的精度为0.01

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

图2.4 有多个测试案例的处理方法。

#include <>

* run this program using the console pauser or add your own getch, system("pause") or input loop */

void shellsort( long *a, long n );

int main()

long n,i,j;

long *a,*b;

double r[100];/用来存放每个测试案例的计算结果 **

j=0;/*记录测试案例的个数 **

***读入用户的输入，若当前输入为负数，则程序终止***

for( n = 0; n >=0 ;

if( n > 0 )

当n为0时，标志相应的r数组值为－1，输出时碰到－1则输出一个空行***

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了