实验二动态规划算法样本

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和丫，当另一序列Z既是X的子序列又是丫的子序列时，称Z是 序列X和丫的公共子序列。给定2个序列X=x1,x2,xm和Y=y1,y2,yn,

2、找出X和丫的最长公共子 序列。三、（1）实验源代码：/最长公共子序问题：问题描述：若给定序列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和丫，当另一序列Z既是X的子序列又是丫的子序列时，称Z 是序列X和丫的公共子序列。/给定2个序列X=x1,x2,xm和Y=y1,y2,yn, 找出X和丫的最长公共 子序列。#include<

3、;bits/stdc+.h>using namespace std;#define max 1000/ 注意: 这里使用的 char 数组, 能够按字符输出 , 若改为 string 类型 ,/ 执行 printf("%c",Am-1) 就会报错 ;char A100,B100; / 输入的两个串 a 和 b/ 这里定义全局变量能够不赋值 0, 因为全局变量自动赋值 0;int cmaxmax; /记录最长公共子序的长度 ;int bmaxmax; /记录状态号 ;void LCS(int m,int n)if(m=0|n=0)return;else if(bmn=1

4、)LCS(m-1,n-1);printf("%c",Am-1);else if(bmn=2)m=m-1;LCS(m,n);else if(bmn=3)n=n-1;LCS(m,n);void LCS_length(int m,int n)for(int i=1;i<=m;i+)for(int j=1;j<=n;j+)if(Ai-1=Bj-1)cij=ci-1j-1+1; bij=1;else if(ci-1j>=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;int main()printf(" 请输入两个待测的

5、字符串 :n");scanf("%s",&A);scanf("%s",&B);int m=strlen(A); /m为 A 串长度 ;int n=strlen(B); /n为 B 串长度 ;LCS_length(m,n);printf(" 其最长公共子序的长度为 :%dn",cmn);printf(" 其最长公共子序为 :");LCS(m,n);return 0;(2) 运行结果为 :算法思路：最长公共子序列的结构有如下表示：设序列X = <x, x 2,x m>®

6、丫=<¥，y 2,y n>的一个最长公共子序列Z=VZi,Z2,z k>,则：1. 若Xfyn,则Zk=Xn=yn且乙-1是Xm-1和Yn-1的最长公共子序列；2. 若Xmyn且ZkXm ,则Z是Xm-1和丫的最长公共子序列；3. 若Xmyn且Zkyn ,则Z是X和1的最长公共子序列。其中 Xm-1 = <X1,X2,Xm-1>,丫 n-1=Vy1, y2,y n-1>, Z k-1 =<Z1, Z2,Z k-1 >o0if / = Oor J =<n.1 ii - I. / - l| + Iif J； j > Omid.*

7、 =.max（叩 Jif f, J > Oandjf 学刃 *基本题二：最大字段和问题实验目的与要求1、 熟悉最长最大字段和问题的算法 ;2、 进一步掌握动态规划算法 ;二、 实验题若给定n个整数组成的序列ai, a2, a3, an,求该序列形如ai + a+i + an的最大值。三 , 实验源代码 : #include<bits/stdc+.h>#define max 1000 using namespace std;int N; / 表示一个数组的长度值 ;int dpmax; / 记录以 i 为结尾的最大子段和 ;/ 经过 dp 数组记录最优下标的 start 和 end;void Maxsum(int a)int maxx=0;int end,start;for(int i=1;i<=N;i+)if(dpi-1>0)dpi=dpi-1+ai;elsedpi=ai; if(maxx<=dpi)maxx=dpi;end=i;sta