实验二动态规划算法.docx

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

1、实验二动态规划算法 基本题一：最长公共子序列问题一、实验目的与要求1、熟悉最长公共子序列问题的算法；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是序列

2、X和Y的公共子序列。给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。 三、程序代码#include"stdlib.h"#includeusingnamespacestd;voidLCSLength(intm,intn,char*x,char*y,int**c,int**b){inti,j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;

3、j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}voidLCS(inti,intj,char*x,int**b){if(i==0

4、

5、j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);printf("%c",x[i]);}elseif(b[i][j

6、]==2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);}constintM=7;constintN=6;voidoutput(char*s,intn);voidLCSLength(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[]={'','A','B','C','B','D','B','C'};cha

7、ry[]={'','B','D','C','D','B','A'};int**c=newint*[M+1];int**b=newint*[M+1];for(inti=0;i<=M;i++){c[i]=newint[N+1];b[i]=newint[N+1];}cout<<"序列X："<

8、、Y最长公共子序列为："<

9、]的值仅由c[i-1][j-1],c[i-1][j]和c[i][j-1]这三个数组元素的值所确定。对于给定的数组元素c[i][j],可以不借助于数组b而仅借助与数组c本身在O(1)时间内确定c[i][j]的值。基本题二：最大字段和问题 一、实验目的与要求1、熟悉最长最大字段和问题的算法；2、进一步掌握动态规划算法；二、实验题   若给定n个整数组成的序列a1，a2，a3，……an，求该序列形如ai＋ai＋1＋……＋an的最大值。三、程序代码#include#defineNUM1001inta[NUM]

10、;intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++){intthissum=0;for(intj=i;j<=n;j++){thissum+=a[j];if(thissum>sum){sum=this