算法设计与分析 实验4.doc

测试过程：（实验中出现的问题、错误、解决方法）这是第一个实验中由于 i 这个变量没有在循环外定义导致的错误，经过改正后程序就能正 常运行了 改正前的程序如下：改正后的程序如下：实验总结： 通过这个实验我对贪心算法有了一定的了解，但是还很是不熟悉，希望在后的学习中能 更深入的学习并掌握这个非常有用且好用的算法签名：2012 年 11 月 21 日评语与成绩：教师签名： 年 月 日洛阳师范学院信息技术学院软件实验报告专业：__网络工程_______课程：_算法设计与分析_______学号 __姓名：___ ___班级：_网络工程___实验名称实验三 贪心算法实例编程实验类型实践课实验时间2012-11-21实验环境计算机一台实验目的与要求：1. 掌握贪心算法的基本思想2. 能够编写用贪心算法解决问题的程序 3. 能对算法的复杂度，可靠性进行分析实验内容：1.要求给出一种作业调度方案，使所给的 n 个作业在尽可能短的时间内由 m 台机器加工处理完成约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理作业不能拆分成更小的子作业输入：输入：第一行：m，n，分别表示机器数和作业数；第二行：n 个整数，分别表示 n 个作业所需的加工时间。

输出：输出：t 表示加工时间提示：调度时间由 m 台机器中，加工时间最长的一个决定，故贪心选择的一个原则应该是：尽可能均衡 m 台机器的负载（参考木桶原理） 2.一辆汽车加满油后可以行驶 N 千米旅途中有若干个加油站若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油并证明你的算法能产生一个最优解输入输入：第一行：n，k,分别表示加满油后可行驶公里数和加油站个数；第二行：k+1 个整数，分别表示起点、k 个加油站、终点之间的距离 输出输出：加油次数实验步骤：（算法描述、源程序、操作步骤和方法）1.要求给出一种作业调度方案，使所给的 n 个作业在尽可能短的时间内由 m 台机器加工处理完成约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理作业不能拆分成更小的子作业输入：输入：第一行：m，n，分别表示机器数和作业数；第二行：n 个整数，分别表示 n 个作业所需的加工时间输出：输出：t 表示加工时间提示：调度时间由 m 台机器中，加工时间最长的一个决定，故贪心选择的一个原则应该是：尽可能均衡 m 台机器的负载（参考木桶原理） 实验程序如下：# include # include using namespace std;typedef struct Job //作业{int ID;int time;}Job;typedef struct JobNode //作业链表的节点{int ID; int time;JobNode *next;}JobNode,*pJobNode;typedef struct Header //链表的表头{int s; //处理机上的时间；JobNode *next;}Header,pHeader;int main(){void QuickSort(Job *job,int left,int right); //将 job 时间排序void outSort(Job *job,int n); //输出排序void display(Header *M,int m); //输出每个每台机器处理的工作序号数int SelectMin(Header *M,int m); //分配作业时选取机器函数；void solve(Header *head,Job*job,int n,int m); //作业分配函数；int m,n; cout>m;Header *head=new Header [m]; //动态构建数组结构体，用于记录机器的作业时间；cout>n;Job *job=new Job [n]; //动态构建作业的数组结构体；cout>job[i].time;job[i].ID=i;}QuickSort(job,0,n-1); //作业排序outSort(job,n); //输出排序solve(head,job,n,m); //作业分配display(head,m); //输出分配coutmiddle)if(ii)QuickSort(job,i,right);}void display(Header *M,int m) //作业分配输出函数；{JobNode *p;for(int i=0;iIDnext;}while(p!=0);}}void outSort(Job *job,int n) //作业时间由大到小排序后输出函数；{couttime=job[i].time;jobnode->ID=job[i].ID;jobnode->next=0;head[i].s=jobnode->time;head[i].next=jobnode;}if(im) {for(int i;itime=job[i].time;jobnode->ID=job[i].ID;jobnode->next=0;k=SelectMin(head,m);p=head[k].next;head[k].s+=jobnode->time;while(p->next!=0)p=p->next;p->next=jobnode;}}}2.一辆汽车加满油后可以行驶 N 千米。

旅途中有若干个加油站若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油并证明你的算法能产生一个最优解输入输入：第一行：n，k,分别表示加满油后可行驶公里数和加油站个数；第二行：k+1 个整数，分别表示起点、k 个加油站、终点之间的距离 输出输出：加油次数 实验程序如下：#include#define N 1000using namespace std; int greedy(int d[],int n,int k) { int num = 0; int i=0;int s=0;for( i = 0;i n) { printf(“no solution\n“); return 0; } } for( i = 0,s = 0;i n) { num++; s = d[i]; } } //printf(“%d\n“,num); cin>>num; return 1; } int main() { int i,n,k; int d[N]; //printf(“请输入汽车可行驶： \n“);cout>n;//printf(“加油站的个数： \n“);cout>k;//scanf(“%d“,for(i=0;i> d[i];//scanf(“%d“,fflush(stdin);}greedy(d,n,k+1); system(“pause“);return 0; }。