内容发布更新时间 : 2024/12/22 14:24:49星期一 下面是文章的全部内容请认真阅读。
《算法分析与设计》实验指导书
本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。 上机实验一般应包括以下几个步骤： （1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。 （2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。 （3）、上机结束后，整理出实验报告。
实验报告应包括： 1） 问题分析 2） 算法描述 3）运行结果、 4）算法性能分析。
实验一
实验名称：贪心算法应用及设计 实验学时：6学时 实验类型：验证 实验目的：
1. 理解贪心算法的基本思想
2. 掌握利用贪心算法求解问题的求解步骤 实验内容
1. 活动选择问题 （2学时） 问题描述：
设有11个会议等待安排，用贪心法找出满足目标要求的会议集合，这些会议按结束时间的非减序排列如下表。 会议i 开始时间bi 结束时间ei 1 1 4 2 3 5 3 0 6 4 5 7 5 3 8 6 5 9 7 6 10 8 8 10 9 8 12 10 2 13 11 12 14 实验实现提示： １) 数据结构设计：
将会议开始时间存储在数组B中，结束时间存储在数组E中，数组下标为会议的代码。结果存储在数组A中，其元素A[i]==true，表示会议i被选中。 ２）算法：
void GreedySelect(int n, struct time B[], struct time E[], bool A[]) {
int i,j;
A[1]=true; j=1; i=2; while( i<=n) if (B[i]>=E[j])
{ A[i]=true; j=i;} else
A[i]=false; }
思考题：证明所得的解是最优解？ 2.单源点最短路径问题。（2学时） 问题描述
如图所示的有向带权图中，求源点0到其余顶点的最短路径及最短路径长度。并对算法进行性能分析。
实现提示
1） 数据结构设计：
将图存储在邻接矩阵C中，结点个数为n，源点编号为u, 源点u到其余顶点的最短路径长度存储在dist[],最短路径存储在p[]。 2) 算法
void Dijkstra(int C[n][n], int n,int u,float dist[],int p[]) { bool s[n];
for( int i=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++) { int temp= ∞; int t=u;
for( int j=1;j<=n;j++)
if ((!s[j])&& dist[j] { t=j; temp=dist[j]；} if (t==u) break; 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中的所有顶点的最短边的权值，即边(j，closest[j])的权值。 b. Kruskal算法 图用带权邻接矩阵C来存储，设置数组bian[]存储图边的权值（按权值从小到大排好序） 2）算法 void Prim( int n, int u0, int c[n][n]) { bool s[n]; int closest[n]; double lowcost[n]; for ( int i=0; i { lowcost[i]=c[u0][i]; closest[i]=u0; s[i]=false; }