算法设计-最长公共子序列动态规划算法
算法设计与分析实验报告
姓名,XXX
班级,XXX
学号,XXX
一、实验名称,最长公共子序列suanfa
时间,2012年3月14日,星期三,第四节
地点,12#311
二、实验目的及要求
最长公共子序列问题,给定两个序列X={x,x …x}和12,mY={y,y, …y} ,找出X和Y的最长公共子序列。 12n
动态规划算法可有效的解此问题。下面按照鼎泰规划算法设计步骤来设计界此问题的有效算法。
三、实验环境
VC++
四、实验内容
出键盘上输入两个字符序列,输出最长公共子序列及其数目。 五、算法描述及实验步骤
设序列x=
和y=的一个最长公共子序列z=,则,
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的最长公共子序列。
六、调试过程及实验结果
void gong_tong(st &a,st &b,sz d[][X]){
int i,j;
for(i=0;i<=a.length;i++)d[i][0].c=0;
for(i=0;i<=b.length;i++)d[0][i].c=0;
for(i=1;i<=a.length;i++){
for(j=1;j<=b.length;j++){
if(a.elem[i-1]==b.elem[j-1]) {
d[i][j].c=d[i-1][j-1].c+1;
strcpy(d[i][j].a,d[i-1][j-1].a);
d[i][j].a[d[i][j].c-1]=b.elem[j-1];
}
else if(d[i-1][j].c>=d[i][j-1].c) {
d[i][j].c=d[i-1][j].c;
strcpy(d[i][j].a,d[i-1][j].a);
}
else {
d[i][j].c=d[i][j-1].c;
strcpy(d[i][j].a,d[i][j-1].a);
}
}
}
printf("最长公共子序列有%d\n",d[a.length][b.length].c);
printf("最长公共子序列是,");
for(i=0;i<=d[a.length][b.length].c;i++)
printf("%c",d[a.length][b.length].a[i]);
}
七、
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
要好好的理解动态规划算法思想,好好的掌握此思想。 八、附录,源程序清单,
#include
#include
#include
#define X 200
#define OVERFLOW -2
int ji_shu(char *a){
int i;
for(i=0;i<=100;i++){
if(a[i]=='\0') break;
else ;
}
return i;
}
typedef struct{
char *elem;
int length;
int listsize;
}st;
typedef struct{
char a[X];
int c;
}sz;
void get_char(st &x){
x.elem=(char *)malloc(X*sizeof(char));
if(!x.elem) exit(OVERFLOW);
x.listsize=X;
gets(x.elem);
x.length=ji_shu(x.elem); }
void get_room(st &d){
d.elem=(char *)malloc(X*sizeof(char));
if(!d.elem) exit(OVERFLOW);
d.listsize=X;
d.length=0;
}
void printf_char(st &x){
int i;
for(i=0;i=d[i][j-1].c) {
d[i][j].c=d[i-1][j].c;
strcpy(d[i][j].a,d[i-1][j].a);
}
else {
d[i][j].c=d[i][j-1].c;
strcpy(d[i][j].a,d[i][j-1].a);
}
}
}
printf("最长公共子序列有%d\n",d[a.length][b.length].c);
printf("最长公共子序列是,");
for(i=0;i<=d[a.length][b.length].c;i++)
printf("%c",d[a.length][b.length].a[i]);
}
void main(){
st x,y;
static sz d[X][X];
printf("请输入第一个字母串X,");
get_char(x);
printf("%d\n",x.length);
printf("请输入第二个字母串Y,");
get_char(y);
printf("%d\n",y.length);
gong_tong(x,y,d);
}
浙公网安备 33021202002483