《算法设计与分析》实验指导书

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

1、算法设计与分析实验指导书邵阳学院信息工程系陈智2014年2月实验1最大子段和（分治法）一、实验内容运用分治法，编制程序求解如下问题：给定由n个整数（可能有负整数）组成的序列（a1,a2,…,an），最大子段和问题要求该序列形如的最大值（1<=i<=j<=n），当序列中所有整数均为负整数时，其最大子段和为0。二、实验要求1．进一步掌握递归算法的设计思想以及递归程序的调式技术；2．理解这样一个观点，分治与递归经常同时应用在算法设计之中。三、主要仪器设备装有TC或VisualC++的PC机四、实验步骤1．算法分析最大子段和问题的分治策略

2、是：（1）划分：按照平衡子问题的原则，将序列(a1,a2,…,an)划分成长度相同的两个子序列(a1,…,an/2)和(an/2＋1,…,an)，则会出现以下三种情况：①a1,…,an的最大子段和＝a1,…,an/2的最大子段和；②a1,…,an的最大子段和＝an/2＋1,…,a的最大子段和；③a1,…,an的最大子段和＝，且（2）求解子问题：对于划分阶段的情况①和②可递归求解，情况③需要分别计算：，则s1+s2为情况③的最大子段和。（3）合并：比较在划分阶段的三种情况下的最大子段和，取三者之中的较大者为原问题的解。分析算法的时间

3、性能，对应划分得到的情况①和②，需要分别递归求解，对应情况③，需要两个并列for循环，时间复杂性是O(n)，所以，存在如下递推式：时间复杂性为O(nlogn)。2．参考代码#includeintMaxSum(inta[],intleft,intright){intsum=0,leftsum=0,rightsum=0;intcenter,i,j;ints1,s2,lefts,rights;if(left==right){//如果序列长度为1，直接求解if(a[left]>0)sum=a[left];elses

4、um=0;}else{center=(left+right)/2;//划分//对应情况①，递归求解leftsum=MaxSum(a,left,center);//对应情况②，递归求解rightsum=MaxSum(a,center+1,right);//以下对应情况③，先求解s1s1=0;lefts=0;for(i=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}//再求解s2s2=0;rights=0;for(j=center+1;j<=right;j++){right

5、s+=a[j];if(rights>s2)s2=rights;}sum=s1+s2;//计算情况③的最大子段和//合并，在sum、leftsum和rightsum中取较大者if(sum

6、行结果。实验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

7、={y1,y2,…,yn}，找出X和Y的最长公共子序列。二、实验要求1．熟悉最长公共子序列问题的算法；2．初步掌握动态规划算法。三、主要仪器设备装有TC或VisualC++的PC机四、实验步骤1．算法分析最长公共子序列问题具有最优子结构性质。设X={x1,...,xm}，Y={y1,...,yn}，及它们的最长子序列Z={z1,...,zk}，则：（1）若xm=yn，则zk=xm=yn，且Z[k-1]是X[m-1]和Y[n-1]的最长公共子序列（2）若xm!=yn，且zk!=xm,则Z是X[m-1]和Y的最长公共子序列（3）若xm

8、!=yn,且zk!=yn,则Z是Y[n-1]和X的最长公共子序列由性质导出子问题的递归结构当i=0,j=0时,c[i][j]=0当i,j>0;xi=yi时,c[i][j]=c[i-1][j-1]+1当i,j>0;xi!=yi时,c[i][j]=ma