实验二动态规划算法

《实验二动态规划算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验二动态规划算法基本题一：最长公共子序列问题一、实验目的与要求1、熟悉最长公共子序列问题的算法：2、初步掌握动态规划算法；二、实验题若给定序列X={xl，x2,…，xm}，则另一序列Z={zl，z2,…，zk}，是X的子序列是指存在一个严格递增卜标序列…，ik}使得对于所有j=l，2,…，k有：zj=xijo例如，序列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={xl，x

2、2,…，xm}和Y={yl，y2,…，yn}，找出X和Y的最长公共子序列。三、程序代码include"stdlib.h"#include

3、+l;b[i][j]=l；}elseif(c[i-l]Lj]>=c[i][j-l]){c[i]U]=c[i-l][j];b[i][j]=2;}else{c[i]lj]=c[i]lj-l]；b卿=3;}}}voidLCS(inti,intj,char*x,int料b)if(i==0

4、

5、j==0)return;if(b[i][j]==I){LCS(i-l，j-l，x，b);printf(H%c"，x[i]);}elseif(b[i][j]==2)LCS(i-l，j，x，b);elseLCS(i，j-l，x，b);}constintM=7;constin

6、tN=6;voidoutput(char*s，intn);voidLCSLcngth(intm，intn，char*x,char*y,int**c,int**b);voidLCS(inti,intj,char*x，int**b);voidmain(){//X={A，B，C，B，D,B，C}//Y={B，D，C，D，B，A}charx[]={*charyU^f'VBVDVCVDVBVA1}；int=newint*[M+1];int**b=newint*[M+1];for(inti=0;i<=M;i++){efi]=newintfN+11;b[i]=n

7、ewint[N+l];}cout«"序列X:"«endl;output(x,M);cout«'•序列Y:"«endl;output(y，N);LCSLength(M，N，x，y，c，b);cout«n序列X、Y最长公共子序列长度为：M«c[M][N]«endl;cout«"序列X、Y最K:公共子序列力："«endl;LCS(M,N，x，b);cout«endl;voidoutput(char*s,intn){for(inti=1;i<=n;i++){cout«s[i]«"}cout«endl;}四、运行结果r，*C:UsersAdministr

8、atorDesktopDebug最长公共子序歹!哼列X:卜BCBDBC哼列V:BDCDBA隆歹1>、V譽长兮g子2歹I伴度为：4睁歹fe、V蕞袅公共子彥歹j为：PCDBpressanykeytocontinue4rrr►分析：①在算法LCSLength屮，由于每个数纟II单元的计算耗吋0(1)吋间，所以，算法LCSLength耗时O(m+n)o②在算法LCS中，每一次递归调用使i或j减1，因此算法的计算时间为O(m+n)。③在算法LCSLength和LCS十，可以将数组b省i，因力，数组元素c[i]U]的值仅由c[i-l]U-l],cli-1

9、仙和cUHj-lj这三个数组元素的值所确定。对于给定的数组元素cU仙X以不借助于数组b而仅借助与数组c本身在0(1)吋间内确定cUUU的值。基本题二：最大字段和问题一、实验目的与要求1、熟悉敁长敁大字段和问题的算法；2、进一步掌握动态规划算法；二、实验题若给定n个整数组成的序列aPa2,a3,……an,求该序列形如ai+ai+1+……+a„的最大值。三、程序代码#include#defineNUM1001intafNUM];intMaxSum(intn,int*a，int&besti，int&bestj)intsum=0;f

10、or(inti=1;i<=n;i++){intthissum=O;for(intj=i;j<=n;j++){thissum