《實(shí)驗(yàn)四 動(dòng)態(tài)規(guī)劃算法》由會(huì)員分享，可在線閱讀，更多相關(guān)《實(shí)驗(yàn)四 動(dòng)態(tài)規(guī)劃算法（4頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
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}使得對(duì)于所有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
2、}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。
三、 實(shí)驗(yàn)提示
include "stdlib.h"
#include "string.h"
void LCSLength(char *x ,char *y,int m,int n, int **c, int **b)
{
int i ,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; j++)
{
if (x[
3、i]==y[j])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
else if (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;
}
}
}
void LCS(int i ,int j, char *x ,int **b)
{
if (i ==0 || j==0) return;
if (b[i][j]== 1)
{
LCS(i-1,j-1,x,b);
printf("%c",x[i
4、]);
}
else if (b[i][j]== 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}，則
(1) 若xm=yn，^zk=xm=yn，且zk-1是xm-1和yn-1的最長公共子序 列。
(2) 若xm/yn且zk/xm，則Z是xm-1和Y的最長公共子序列。
(3) 若xm/yn且zk/yn，則Z是X和yn-1的最長公共子序列。
由此可見，2個(gè)序列的最長公共子序列包含了這2個(gè)序列的前綴 的最長公共子序列
5、。因此，最長公共子序列問題具有最優(yōu)子結(jié) 構(gòu)性質(zhì)。
實(shí)驗(yàn)代碼：
#include "stdafx.h”
#include
#include
#include
#include
using namespace std;
#define N 105
int dp[N+1][N+1];
char str1[N] , str2[N];
int maxx(int a , int b)
{
if(a > b)
return a ;
return b ;
}
int LCSL(int len1 ,
6、 int len2)
{
int i , j ;
int len = maxx(len1 , len2);
for ( i = 0 ; i <= len; i++ ) {
dp[i][0] = 0
dp[0][i] = 0
}
for ( i = 1 ; i<= lenl ; i++)
for( j = 1 ; j <= len2 ; j++)
{
if (str1[i - 1] == str2[j - 1])
{
dp[i][j] = dp[i - 1][ j - 1] + 1 ;
}
else
{
dp[i][j] = maxx(dp[i - 1][ j
7、] , dp[i][j - 1]);
}
}
return dp[len1][len2];
}
void LCS(int i, int j)
{
if(i==-1||j==-1) return ;
if (str1[i]==str2[j])
{
LCS(i-1,j-1);
printf("%c ”,str1[i]);
}
else if(dp[i-1][j]>dp[i][j-1])
LCS(i-1,j);
else
LCS(i,j-1);
}
int main()
{
while (cin >> str1 >> str2)
{
int len1 = strlen(str1) ;
int len2 = strlen(str2) ;
cout<
實(shí)驗(yàn)四 動(dòng)態(tài)規(guī)劃算法
