最长公共子序列1
最长公共子序列
一、实验目的
1(掌握动态规划算法的基本概念和两个基本要素
2(熟练掌握动态规划算法解决问题的基本步骤。
3(学会利用动态规划算法解决实际问题。
二、实验内容
问题描述:对于给定的两个序列X,Y(长度不大于100)～求它们的最长公
共子序列～试编程实现。
三、实验步骤
?、数据结构与核心算法的设计描述
提示:c[M][N]和b[M][N]及算法参考教材
计算最优化:存储与的最长公共子序列的长度，
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
的值是由那一个子问题得到的。
问题的最优值，即和的最长公共子序列的长度记录于中。
void LcsLength(char x[], char y[], int m, int n, int c[][], int b[][])
{
for(int i = 0; i <= m; i++)
c[i][0] = 0;
for(int j = 1; j <= n; j++)
c[0][j] = 0;
for(i = 1; i<= m; i++)
for(j = 1; j <= n; j++)
{
if(x[i-1] == y[j-1])
{
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;
}
}
}
在算法Lcslength中，由于每个数组单元的计算耗费O(1),故算法耗时O(mn)。
构造最长公共子序列:从开始，依其值在数组b中搜索。当=1时，表示和的最长公共子序列是由和的最长公共子序列在尾部加上所得到的子序列;当=2时，表示和的最长公共子序列与和的最长公共子序列相同;=3时，表示和的最长公共子序列与和的最长公共子序列相同。
void LCS(int b[][], char x[], int i, int j) {
if(i == 0 || j == 0)
return;
if(b[i][j] == 1)
{
LCS(b, x, i-1, j-1);
printf("%c", x[i-1]);
}
else if(b[i][j] == 2)
LCS(b, x, i-1, j);
else
LCS(b, x, i, j-1);
}
在算法LCS中，每一次递归调用使i或j减1，因此算法的计算时间为O(m+n)。
?、函数调用及主函数设计
, 可用函数的调用关系图说明,
主函数
LCSLength LCS
? 程序调试及运行结果分析
最长公共子序列最后总是多个a
? 实验
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
通过本次实验～进一步了解了动态规划算法的使用～在主函数调用这部分还需改进。
四、主要算法
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
图及程序清单
1、主要算法流程图:
初始化函数
LCSLength
LCS
主函数调用
2、程序清单
#include "stdafx.h"
#include"string.h"
#include
using namespace std;
#define M 10
#define N 10
char c[M][N];
char b[M][N];
void LCSLength(int m, int n, char *x, char *y, int c[][N], int b[][N])
{
char 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[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[][N]){
if (i == 0 || j == 0)return;
if (b[i][j] == 1){ LCS(i - 1, j - 1, x, b); cout << x[i]; }
else if (b[i][j] == 2)LCS(i - 1, j, x, b);
else LCS(i, j - 1, x, b);
}
int main()
{
char x[N];
char y[N];
printf("请输入第一组序列: ");
gets(x);
printf("请输入第二组序列: ");
gets(y);
int b[N][N];
int c[N][N];
int m, n;
m = strlen(x);
n = strlen(y);
printf("最长公共子序列为:");
LCSLength(m, n, x, y, c, b);
LCS(m, n, x, b);
printf("\n长度为:%d\n", c[m][n]-1);
return 0;
}
浙公网安备 33021202002483