算法分析与设计试验指导书

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

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

3、ruct time B, struct time E, bool A) (int i,j;A1=true;j=1； i=2;while( i<=n) if (Bi>=Ej) Ai=true; j=i; elseAi=false;思考题：证明所得的解是最优解？2 .单源点最短路径问题。(2学时)问题描述如图所示的有向带权图中，求源点 0到其余顶点的最短路径及最短路径长度。并对算法 进行性能分析。实现提示1)数据结构设计：将图存储在邻接矩阵C中，结点个数为n,源点编号为u,源点u到其余顶点的最短路径长度存储在dist口,最短路径存储在p口。2)算法void Dijkstra(int C

4、nn, int n,int u,float dist,int p) bool sn;for( int i=1; i<=n; i+) disti=Cui;si=false;if (disti= 0°)Pi=-1;elsePi=u;pu=-1;su=true;for( i=1; i<=n; i+) int temp= 00;int t=u;for( int j=1;j<=n;j+)if (!sj)&& distj<temp) t=j; temp=distj ; if (t=u) break;st=true;for( j=1; j<=n;j+)

5、if(!sj)&& Ctj<8)if(distj>(distt+Ctj) distj= distt+Ctj; pj=t;思考题：算法在何种情况下得不到原问题的解3 .最小生成树问题(2学时)问题描述任选一种贪心算法(Prim或Kruskal)对图所示的无向连通带权图构造一棵最小生成树。 并对算法进行复杂性分析实现提示1)数据结构a. Prim 算法：图用带权邻接矩阵 C来存储，设置数组closest口存储U中的最近邻接顶点和lowcost口 存储U中的所有顶点的最短边的权值，即边 (j, closestj)的权值。b. Kruskal 算法图用带权邻接矩阵C来存储，

6、设置数组 bian存储图边的权值(按权值从小到大排好序)2)算法void Prim( int n, int u0, int cnn) bool sn;int closestn;double lowcostn;for ( int i=0; i<n; i+)if (i!=u0) lowcosti=cu0i;closesti=u0; si=false; for(i=0; i<n; i+) double temp= 00;int t=u0;for ( int j=0；j<n；j+)if (!sj)&& lowcostj<temp) t=j; temp=lowco

7、stj;if (t=u0) break;st=true;for( j=0;j<n; j+)if (!sj)&& ctj<lowcostj) lowcostj= ctj;closestj=t;void Kruskal( int n, struct edge bian, int cnn) int nodesetn;int count=1; bool flagn+1;if (n=1)return;for ( int i=1; i<=n; i+) nodeseti=i; flagi=false;for (int j=1; j<=n; j+) if( cij<

8、; 8) biancount.u=i; biancount.v=j;biancount.weight=cij;count+;sort( bian+1,bian+count);count=1; int edgeset=0; int w=0;while (edgeset<(n-1)if(!flagbiancount.u)&&(flagbiancount.v) w+=biancount.weight; edgeset+ ;flagbiancount.u=true;nodesetbiancount.u=nodesetbiancount.v;else if(flagbiancoun

9、t.u)&&(!flagbiancount.v) w+=biancount.weight; edgeset+ ;flagbiancount.v=true;nodesetbiancount.v=nodesetbiancount.u;else if(!flagbiancount.u)&&(!flagbiancount.v) w+=biancount.weight; edgeset+ ;flagbiancount.u= flagbiancount.v=true; nodesetbiancount.u=nodesetbiancount.v;)elseif(nodeset

10、biancount.u!=nodesetbiancount.v) w+=biancount.weight; edgeset+ ;int tmp= nodesetbiancount.v;for( int i=1; i<=n; i+)if (nodeseti=tmp)nodeseti=nodesetbiancount.u;)count+;)实验二实验名称：分治法算法应用及设计实验学时：4学时实验类型：验证实验目的：1 .理解分治法算法的基本思想2 .掌握利用分治法算法求解问题的求解步骤实验内容1 .二分检索(2学时)问题描述：设a0:n-1是一个已排好序的数组。请改写二分搜索算法，使得当搜索

11、元素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(datam=key)return h;if(datam>key)return besearch(l,m-1,data,key

12、); 在 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=datal;/datal为划分基准元素

13、while ( i<j)(while( i<j && dataj>=pivot)j-;if( i<j) swap(datai,dataj); / 交换 datai,dataj i+;)while( i<j && datai<=pivot) i+;if( i<j) swap(datai,dataj); / 交换 datai,dataj j-;) return j;)void QuickSort( int l,int h; int data)int pivotpos;if( l<h)pivotpos=Pation(l,

14、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)是可乘的。用加括号的 方法表示矩阵连乘的次序，不同加括号的方法所对应的计算次序是不同的。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数

15、乘次数最少。实现提示1)数据结构设计采用数组m来存放各个子问题的最优值，数组s来存放各个子问题的最优决策；2 )算法void MatrixChain(int *p, int n,int *m,int *s) for ( int i=1;i<=n;i+) mij=0; s皿=0;for( int r=2; r<=n; r+)for(int i=1; i<=n-r+1; i+) int j=i+r-1;mij=mi+1j+pi-1*pi*pj;s皿-i;for( int k=i+1; k<j; k+) int t=mik+mk+1j+pi-1*pk*pj;if ( t<

16、;mij) mij=t; sij=k; void Traceback(int i, int j, int *s)if ( i=j) return ;Traceback( i,sij,s);Traceback( sij+1,j,s);cout<< A"<< '<<i<< :'"<<sij<<'<< "乘以"<< A"<< '<<sij+1<<:"><<j&l

17、t;<<<endl;2.最长公共子序列问题(2学时)问题描述：若给定序列X=x1,x2，,xm,则另一序列 Z=z1,z2,zk,是X的子序列是指存在一个 严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B , C, D, B是序列X=A, B, C, B, D, A, B的子序列，相应的递增下标序列为2, 3, 5, 7。给定2个序列X和Y,当另一序列Z既是X的子序列又是 Y的子序列时，称Z是序列X和Y的公 共子序列。给定2个序列X=x1,x2，,xm Y=y1,y2,yn,找出X和Y的最长公共子序列。 实现提示1)数据结构设计采用

18、数组c来存放各个子问题的最优值，数组 b来存放各个子问题最优值的来源。数组 x1:m和y1:n分别存放X序列和Y序列2 )算法void LCSLength( int m,int n,char *x,char *y,int *c,int *b) int i,j;for( i=1; i<=m; i+) ci0=0;for( i=1;i<=m;i+) c0i=0;for( i=1; i<=m; i+)for(j=1; j<=n; j+) if ( xi=yj) cij=ci-1j-1+1;bij=1;else if( ci-1j>=cij-1) cij=ci-1j; b皿=3; else cij=cij-1; bij=2;void LCS( int i,int j, char *x,int *b) if( i=0 | j=0) return;if( bij=1) LCS(i-1,j-1,x,b) cout<<xi;else if ( bij=2)LCS(i,j-1,x,b) elseLCS(i-1,j,x,b) 3.0-1背包问题 (2学时) 问题描述：试用动态规划方法求解0-1背包问题并编程在计算机上实现，同