实验一:最长公共子序列问题
一、实验目的与要求
1、明确子序列公共子序列的概念
2、最长公共子序列(Longest Common Subsequence,简称LCS) 的概念 3、利用动态规划解决最长公共子序列问题
二、实验题:
问题描述:字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1, ,xm-1”,序列Y=“y0,y1, ,yk-1”是X的子序列,存在X的一个严格递增下标序列<i0,i1, ,ik-1>,使得对所有的j=0,1, ,k-1,有xij=yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。
给定两个序列A和B,称序列Z是A和B的公共子序列,是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。
三、实验代码
#include<stdlib.h> #include<stdio.h> #include<string.h> #define Size 100
void LCSLength(int m,int n,char *x,char *y,int c[Size][Size],int b[Size][Size]) { int i,j;
for(i=1;i<=m+1;i++) c[i][0]=0; for(i=1;i<=n+1;i++) c[0][i]=0; for(i=1;i<=m+1;i++) for(j=1;j<=n+1;j++) { if(x[i]==y[j])
{ c[i][j]=c[i-1][j-1]+1; b[i][j]=0; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=1; }
else { c[i][j]=c[i][j-1]; b[i][j]=2; } }
}
void LCS(int i,int j,char *x,int b[Size][Size]) { if(i==0||j==0) return; if(b[i][j]==0)
{ LCS(i-1,j-1,x,b); printf("%c",x[i]); } else if(b[i][j]==1) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); }
main()
计算机算法设计与分析 实验报告 专学姓 业: 测试技术 10-01 号: 54101311 名: XXX 指导老师: 宋胜利 实验一:棋盘覆盖一、实验目的与要求 1、理解算法的概念 ...
贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告课程名称:算法设计与分析 姓名: 熊齐超 实验序号:一 班级:软件 121 学号:1208060220 实验日期:2014/11...
华北电力大学科技学院 实验报告 实验名称 课程名称 算法设计与分析算法设计与分析 专业班级:计算机 10k1 学号:101909010121 学生姓名:孙刚成绩: 实验...
计算机算法与设计分析 计算机算法与设计分析 实验报告 班级: 姓名: 学号: 目录实验一 分治与递归 ………1 1、基本递归算法………1 2、棋盘覆盖问题………...
计算机算法与设计分析实验报告 隐藏>> 计算机算法与设计分析 实验报告 班级: 姓名: 学号: 目录实验一 分治与递归 ???1 1、基本递归算法???1 2、棋盘覆盖问题...
计算机算法设计实验报告_IT/计算机_专业资料。课程名: 课程名:计算机算法设计与分析 实验一 分治法的应用——快速排序 分治法的应用——快速排序 —— 一 实验目的...
分支限界法 32页 2财富值 第七章 分支限界法 28页 1财富值 算法设计与分析实验报告手... 54页 1财富值 计算机算法设计与分析【王... 90页 1财富值...
洛阳师范学院信息技术学院 软件实验报告专业:网络工程(物联网方向)课程:计算机算法设计与分析 学号:111124092 姓名:朱玉付班级:11 级网工物联 实验名称 实验类型 ...
组 计算机算法设计与分析 课 教师评定 学号 2007102×× 姓名 121 实验日期 哈夫曼编码问题 1、 、 实验目的: 实验目的:根据最优二叉树构造哈夫曼编码 利用哈...
热门文档