动态规划算法应用

《动态规划算法应用》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、宁夏师范学院数学与计算机科学学院《算法设计与分析》实验报告实验序号：　　　　　　　　　　实验项目名称：动态规划算法应用学　　号06姓　　名赵正平专业、班10计本班实验地点321指导教师马涛时间2013-4-18一、实验目的与要求(1)、熟悉最长公共子序列问题的算法；(2)、初步掌握动态规划算法；二、实验设备（环境）及要求1、环境要求：硬件：PC（PII以上，128M以上内存）、因特网接入；软件：WindowsXP操作系统、Office2003、多媒体播放软件。三、实验内容与步骤若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序

2、列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。四、实验结果与数据处理#include#defineM6#defineN6intc[N][M];intb[N][M];intIcsLength(charx[],chary[]){intm=M-

3、1;intn=N-1;inti,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;}elseif(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;}}returnc[m][n];}intIcs(inti,intj,charx[]){if(i==0

4、

5、j=

6、=0)return0;if(b[i][j]==1){Ics(i-1,j-1,x);printf("%c",x[i]);}elseif(b[i][j]==2)Ics(i-1,j,x);elseIcs(i,j-1,x);return0;}voidmain(){charx[]={'A','0','C','B','D','A','B'};chary[]={'0','B','D','C','A','B','A'};inti,j;printf("长度为%d",IcsLength(x,y));for(i=0;i

7、]);}printf("");}for(i=0;i

8、一个子问题的解得到的，这在构造最长公共子序列时要用到结论：由于每个数组单元的计算耗费O（1）时间，算法lcsLength耗时O（mn）六、教师评语。签名：日期：年月日成绩