算法分析与设计实验指导书.doc

《算法分析与设计实验指导书.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.《算法分析与设计》实验指导书本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。上机实验一般应包括以下几个步骤：（1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。（2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。（3）、上机结束后，整理出实验报告。实验报告应包括：1）问题分析2）算法描述3）运行结果、4）算法性能分析。实验一实验名称：贪心算法应用及

2、设计实验学时：6学时实验类型：验证实验目的：1.理解贪心算法的基本思想.1.掌握利用贪心算法求解问题的求解步骤实验容1.活动选择问题　　（2学时）问题描述：　设有11个会议等待安排，用贪心法找出满足目标要求的会议集合，这些会议按结束时间的非减序排列如下表。会议i1234567891011开始时间bi130535688212结束时间ei4567891010121314实验实现提示：１)数据结构设计：　　　将会议开始时间存储在数组B中，结束时间存储在数组E中，数组下标为会议的代码。结果存储在数组A中，其元素A[i]==true，表示会议i被选中。２）算法：voidGreedySel

3、ect(intn,structtimeB[],structtimeE[],boolA[]){inti,j;A[1]=true;j=1;i=2;while(i<=n)if(B[i]>=E[j]){A[i]=true;j=i;}elseA[i]=false;}思考题：证明所得的解是最优解？2.单源点最短路径问题。（2学时）.问题描述如图所示的有向带权图中，求源点0到其余顶点的最短路径及最短路径长度。并对算法进行性能分析。 实现提示1）数据结构设计：　　　将图存储在邻接矩阵C中，结点个数为n，源点编号为u,源点u到其余顶点的最短路径长度存储在dist[],最短路径存储在p[]。2)算

4、法voidDijkstra(intC[n][n],intn,intu,floatdist[],intp[]) {bools[n]; for(inti=1;i<=n;i++) {dist[i]=C[u][i]; s[i]=false; if(dist[i]=∞) p[i]=-1; else p[i]=u; } p[u]=-1; s[u]=true; for(i=1;i<=n;i++) {inttemp=∞; intt=u; for(intj=1;j<=n;j++) if((!s[j])&&dist[j]

5、ak; s[t]=true; for(j=1;j<=n;j++) if((!s[j])&&C[t][j]<∞) if(dist[j]>(dist[t]+C[t][j]) {dist[j]=dist[t]+C[t][j];p[j]=t;} } }思考题：算法在何种情况下得不到原问题的解3.最小生成树问题（2学时）问题描述任选一种贪心算法（Prim或Kruskal）对图所示的无向连通带权图构造一棵最小生成树。并对算法进行复杂性分析实现提示1）数据结构a.Prim算法：图用带权邻接矩阵C来存储，设置数组closest[]存储U中的最近邻接顶点和lowcost[]存储U中的所有顶点的最

6、短边的权值，即边(j，closest[j])的权值。b.Kruskal算法图用带权邻接矩阵C来存储，设置数组bian[]存储图边的权值（按权值从小到大排好序）2）算法.voidPrim(intn,intu0,intc[n][n]) {bools[n]; intclosest[n]; doublelowcost[n]; for(inti=0;i

7、;j