算法设计与分析 实验4

《算法设计与分析 实验4》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、测试过程：（实验中出现的问题、错误、解决方法）这是第一个实验中由于i这个变量没有在循环外定义导致的错误，经过改正后程序就能正常运行了。改正前的程序如下：改正后的程序如下：实验总结：通过这个实验我对贪心算法有了一定的了解，但是还很是不熟悉，希望在后的学习中能更深入的学习并掌握这个非常有用且好用的算法。签名：2012年11月21日评语与成绩：教师签名：年月日洛阳师范学院信息技术学院软件实验报告专业：__网络工程_______课程：_算法设计与分析_______学号__姓名：______班级：_网络工程___实验名称实验三

2、贪心算法实例编程实验类型实践课实验时间2012-11-21实验环境计算机一台实验目的与要求：1.掌握贪心算法的基本思想。2.能够编写用贪心算法解决问题的程序。3.能对算法的复杂度，可靠性进行分析。实验内容：1.要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。输入：第一行：m，n，分别表示机器数和作业数；第二行：n个整数，分别表示n个作业所需的加工时间。输出：t表示加工时间。提示：调度时

3、间由m台机器中，加工时间最长的一个决定，故贪心选择的一个原则应该是：尽可能均衡m台机器的负载（参考木桶原理）。2.一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。并证明你的算法能产生一个最优解。输入：第一行：n，k,分别表示加满油后可行驶公里数和加油站个数；第二行：k+1个整数，分别表示起点、k个加油站、终点之间的距离。输出：加油次数。实验步骤：（算法描述、源程序、操作步骤和方法）1.要求给出一种作业调度方案，使所给的n个作业在尽可能短的

4、时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。输入：第一行：m，n，分别表示机器数和作业数；第二行：n个整数，分别表示n个作业所需的加工时间。输出：t表示加工时间。提示：调度时间由m台机器中，加工时间最长的一个决定，故贪心选择的一个原则应该是：尽可能均衡m台机器的负载（参考木桶原理）。实验程序如下：#include#includeusingnamespacestd;typedefstructJob/

5、/作业{intID;inttime;}Job;typedefstructJobNode//作业链表的节点{intID;inttime;JobNode*next;}JobNode,*pJobNode;typedefstructHeader//链表的表头{ints;//处理机上的时间；JobNode*next;}Header,pHeader;intmain(){voidQuickSort(Job*job,intleft,intright);//将job时间排序voidoutSort(Job*job,intn);//输出排

6、序voiddisplay(Header*M,intm);//输出每个每台机器处理的工作序号数intSelectMin(Header*M,intm);//分配作业时选取机器函数；voidsolve(Header*head,Job*job,intn,intm);//作业分配函数；intm,n;cout<<"请输入机器台数m:";cin>>m;Header*head=newHeader[m];//动态构建数组结构体，用于记录机器的作业时间；cout<<"请输入作业个数n:";cin>>n;Job*job=newJob[n]

7、;//动态构建作业的数组结构体；cout<<"请按序号输入每个作业调度所需时间time：";for(inti=0;i>job[i].time;job[i].ID=i;}QuickSort(job,0,n-1);//作业排序outSort(job,n);//输出排序solve(head,job,n,m);//作业分配display(head,m);//输出分配cout<

8、{intk=0;for(inti=1;i