《算法分析与设计》实验指导书本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导,其目的是使学生消化理论知识,加深对讲授容的理解,尤其是一些算法的实现及其应用,培养学生独立编程和调试程序的能力,使学生对算法的分析与设计有更深刻的认识。
上机实验一般应包括以下几个步骤:(1)、准备好上机所需的程序。
手编程序应书写整齐,并经人工检查无误后才能上机。
(2)、上机输入和调试自己所编的程序。
一人一组,独立上机调试,上机时出现的问题,最好独立解决。
(3)、上机结束后,整理出实验报告。
实验报告应包括:1)问题分析2)算法描述3)运行结果、4)算法性能分析。
实验一实验名称:贪心算法应用及设计实验学时:6学时实验类型:验证实验目的:1.理解贪心算法的基本思想2.掌握利用贪心算法求解问题的求解步骤实验容1.活动选择问题(2学时)问题描述:设有11个会议等待安排,用贪心法找出满足目标要求的会议集合,这些会议按结束时间的非减序排列如下表。
实验实现提示:1)数据结构设计:将会议开始时间存储在数组B中,结束时间存储在数组E中,数组下标为会议的代码。
结果存储在数组A中,其元素A[i]==true,表示会议i被选中。
2)算法: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;}elseA[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;elsep[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]<temp){ 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<n; i++)if (i!=u0){ lowcost[i]=c[u0][i];closest[i]=u0;s[i]=false;}for(i=0; i<n; i++){ double temp=∞;int t=u0;for ( int j=0;j<n;j++)if ((!s[j])&& lowcost[j]<temp){ t=j; temp=lowcost[j];}if (t==u0) break;s[t]=true;for( j=0;j<n; j++)if ((!s[j])&& c[t][j]<lowcost[j]){ lowcost[j]= c[t][j];closest[j]=t;}}}void Kruskal( int n, struct edge bian[], int c[n][n]){ int nodeset[n];int count=1; bool flag[n+1];if (n==1)return;for ( int i=1; i<=n; i++){ nodeset[i]=i; flag[i]=false;for (int j=1; j<=n; j++){ if( c[i][j]<∞){ bian[count].u=i; bian[count].v=j;bian[count].weight=c[i][j];count++;}}sort( bian+1,bian+count);count=1; int edgeset=0; int w=0;while (edgeset<(n-1)){if(!flag[bian[count].u])&&(flag[bian[count].v])){ w+=bian[count].weight; edgeset++;flag[bian[count].u]=true;nodeset[bian[count].u]=nodeset[bian[count].v];}else if(flag[bian[count].u])&&(!flag[bian[count].v])) { w+=bian[count].weight; edgeset++;flag[bian[count].v]=true;nodeset[bian[count].v]=nodeset[bian[count].u];}else if(!flag[bian[count].u])&&(!flag[bian[count].v])){ w+=bian[count].weight; edgeset++;flag[bian[count].u]= flag[bian[count].v]=true;nodeset[bian[count].u]=nodeset[bian[count].v];}elseif(nodeset[bian[count].u]!=nodeset[bian[count].v]){ w+=bian[count].weight; edgeset++;int tmp= nodeset[bian[count].v];for( int i=1; i<=n; i++)if (nodeset[i]==tmp)nodeset[i]=nodeset[bian[count].u];}count++;}}实验二实验名称:分治法算法应用及设计实验学时:4学时实验类型:验证实验目的:1.理解分治法算法的基本思想2.掌握利用分治法算法求解问题的求解步骤实验容1.二分检索(2学时)问题描述:设a[0:n-1]是一个已排好序的数组。
请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置i和大于x的最小元素位置j。
当搜索元素在数组中时,i和j相同,均为x在数组中的位置。
实验实现提示:1)数据结构设计:将待查数据集合存储在数组data中,用l表示查找围的下界,h表示查找围的上界。
注意查找失败的条件设置:即查找空间为空区间。
2)二分搜索算法:int besearch(int l,int h,int data[],int key){int m; //m=l与h的中点if(l>h)return 失败;if(data[m]==key)return h;if(data[m]>key)return besearch(l,m-1,data,key);//在l至m-1找elsereturn besearch(m+1,l,data,key); //在m+1至h找}思考题:如何将递归算法改为非递归算法?2.快速排序(2学时)问题描述:利用分治法,实现对n个元素进行排序的算法,在计算机上编程实现,同时进行时间复杂性分析。
实验实现提示:1)数据结构设计:将待排序数据集合存储在数组data中,用l表示待排序围的下界,h表示待排序围的上界。
注意排序结束的条件设置:即待排序空间为空区间。
2)算法:int Partion(int l,int h,int data[]){int i=l,j=h,pivot=data[l];//data[l]为划分基准元素while ( i<j){while( i<j && data[j]>=pivot)j--;if( i<j){ swap(data[i],data[j]); //交换data[i],data[j]i++;}while( i<j && data[i]<=pivot)i++;if( i<j){ swap(data[i],data[j]); //交换data[i],data[j]j--;}}return j;}void QuickSort( int l,int h; int data[]){int pivotpos;if( l<h){pivotpos=Pation(l,h,data);QuickSort(l,pivotpos-1,data);QuickSort(pivotpos+1,h,data);}}思考题:本算法的空间的复杂度?实验三实验名称:动态规划算法应用及设计实验学时:6学时实验类型:验证实验目的:1.理解动态规划算法的基本思想2.掌握利用动态规划算法求解问题的求解步骤实验容1.矩阵连乘问题(2学时)问题描述给定n个矩阵{A1,A2,A3,…,An},其中Ai与Ai+1(i=1,2,3, …,n-1)是可乘的。
用加括号的方法表示矩阵连乘的次序,不同加括号的方法所对应的计算次序是不同的。