1、 数 据 结 构 课 程 设 计数 据 结 构 课 程 设 计 贪心算法贪心算法 专业专业 软件工程软件工程 班级班级 B 软件软件 121 学号学号 学生姓名学生姓名 数据结构课程设计贪心算法：任务调度问题 目目 录录 1 设计题目 . 1 2 设计分析 . 1 3 设计实现 . 4 4 测试方法 . 7 4.1 测试目的 7 4.2 测试输入 . 7 4.3 正确输出 . 7 4.4 实际输出 . 7 5 分析与探讨 . 8 5.1 测试结果分析 . 8 5.2 探讨与改进 . 8 6 设计小结 . 8 数据结构课程设计贪心算法：任务调度问题 1 1 设计题目 有n项任务，要求按顺序执行，
2、并设定第i项任务需要ti单位时间。如果任务 完成的顺序为1，2，n，那么第i项任务完成的时间为ci=t1+ti，平 均完成时间（Average Completion Time，ACT）即为（c1+cn）/n。本题要 求找到最小的任务平均时间。 输入要求： 输入数据中包含几个测试案例。每一个案例的第一行给出一个不大于2000000 的整数n，接着下面一行开始列出n个非负整数t（t=0;) /*当 n小于 0 的时候，退出程序*/ scanf(“%ld”, if(n0) 建立一个具有 n个元素的数组； for(i=0;i1），把数组的全部元素分成d1个组。所有距离为 d1的倍数的记录放在同一个组中
3、。先在各组内进行直接插入排序；然后，取第二个 增量d21; increment0; increment=1 ) /*每次的步长都是通过n值右移位来得到的*/ for(i = increment; i =increment; j-= increment) if( temp = 0 ; ) double r100; /*用来存放每个测试案例的计算结果*/ j=0; /*记录测试案例的个数*/ for(对每一个测试案例) 把计算得到的最优调度时间放入 rj中； j+; /*当输入的 n值为负数时。跳出上面的 for 循环*/ for(从 0 到 j) if(ri=-1)printf(“n“);/*输
4、出一个空行*/ else printf( “%.2fn“, ri );/*输出的结果要求精确到0.01*/ 数据结构课程设计贪心算法：任务调度问题 5 scanf( “%ld“, if(n 2000000) printf(“too much for the project!n“); exit(0); if( n 0 ) b = (long*)malloc( n * sizeof( long ) ); a = b; for(i=0; i 1000000000) printf(“too much for the project!n“); exit(0); /* 对输入中出现任务时间为负数的异常处理
5、 */ if(*(b+i) 0 ; i-,a+ ) rj+= (double)*a/(double)n * i; j+; free( b ); 数据结构课程设计贪心算法：任务调度问题 6 /* 当n为0时，标志相应的r数组值为1，输出时碰到1则输出一 个空行*/ else if ( n = 0 ) rj+=-1; for(i=0;i1; increment0; increment=1 ) for(i = increment; i =increment; j-= increment) if( temp *(a + (j-increment) ) *(a+j)= *( a+ (j-incremen
6、t) ); else break; 数据结构课程设计贪心算法：任务调度问题 7 *(a+j) = temp; 4 测试方法 4.1 测试目的 检验程序是否正常运行并完成算法的要求。 4.2 测试输入 4 4 1 2 3 5 2 3 4 1 5 -1 4.3 正确输出 5.00 7.00 4.4 实际输出 数据结构课程设计贪心算法：任务调度问题 8 5 分析与探讨 5.1 测试结果分析 调试与运行过程中，程序可以正常运行，并在输入不同数据情况下分别给出正 确的结果，说明该程序正确无误，完成了此次课程设计题目的要求。 5.2 探讨与改进 总的来说，该程序已基本实现了贪心算法的要求功能，但还可以对其中的一些 细节进行优化，比如程序的运行结果界面可以加上更多的文字描述与提示，增加观 赏性，也可以用起来更方
