资源描述:
《动态规划算法应用》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
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;i7、]);}printf("");}for(i=0;i8、一个子问题的解得到的,这在构造最长公共子序列时要用到结论:由于每个数组单元的计算耗费O(1)时间,算法lcsLength耗时O(mn)六、教师评语。签名:日期:年月日成绩