實(shí)驗(yàn)四 動(dòng)態(tài)規(guī)劃算法

1、實(shí)驗(yàn)四動(dòng)態(tài)規(guī)劃算法一、實(shí)驗(yàn)?zāi)康呐c要求1、熟悉最長公共子序列問題的算法；2、初步掌握動(dòng)態(tài)規(guī)劃算法；二、實(shí)驗(yàn)題若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存 在一個(gè)嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對于所有j=1,2,k有：zj=xij。例如，序列 Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標(biāo)序列為2, 3， 5， 7。給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X 和Y的公共子序列。給定2個(gè)序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。三、實(shí)驗(yàn)提示include s

2、tdlib.h#include string.hvoid LCSLength(char *x ,char *y,int m,int n, int *c, int *b)int i ,j;for (i = 1; i = m; i+) ci0 = 0;for (i = 1; i = n; i+) c0i = 0;for (i = 1; i = m; i+)for (j = 1; j =cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;void LCS(int i ,int j, char *x ,int *b)if (i =0 | j=0) return;if (

3、bij= 1)LCS(i-1,j-1,x,b);printf(%c,xi);else if (bij= 2)LCS(i-1,j,x,b);else LCS(i,j-1,x,b);實(shí)現(xiàn)思路：設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,，zk，則若xm=yn，zk=xm=yn，且zk-1是xm-1和yn-1的最長公共子序 列。若xm/yn且zk/xm，則Z是xm-1和Y的最長公共子序列。若xm/yn且zk/yn，則Z是X和yn-1的最長公共子序列。由此可見，2個(gè)序列的最長公共子序列包含了這2個(gè)序列的前綴 的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)

4、構(gòu)性質(zhì)。實(shí)驗(yàn)代碼：#include stdafx.h”#include #include #include#includeusing namespace std;#define N 105int dpN+1N+1;char str1N , str2N;int maxx(int a , int b)if(a b)return a ;return b ;int LCSL(int len1 , int len2)int i , j ;int len = maxx(len1 , len2);for ( i = 0 ; i = len; i+ ) dpi0 = 0dp0i = 0for ( i = 1 ; i= lenl ; i+)for( j = 1 ; j dpij-1)LCS(i-1,j);elseLCS(i,j-1);int main()while (cin str1 str2)int len1 = strlen(str1) ;int len2 = strlen(str2) ;coutLCSL(len1 , len2)endl;LCS(len1,len2);return 0;實(shí)驗(yàn)