动态规划算法应用.doc_第1页
动态规划算法应用.doc_第2页
动态规划算法应用.doc_第3页
动态规划算法应用.doc_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

宁夏师范学院数学与计算机科学学院算法设计与分析实验报告实验序号：实验项目名称：动态规划算法应用学号06姓名赵正平专业、班10计本班实验地点321指导教师马 涛时间2013-4-18一、实验目的与要求(1)、熟悉最长公共子序列问题的算法；(2)、初步掌握动态规划算法；二、实验设备（环境）及要求1、环境要求：硬件：PC（PII以上，128M以上内存）、因特网接入；软件：Windows XP操作系统、Office2003、多媒体播放软件。三、实验内容与步骤若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列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#define M 6#define N 6int cNM;int bNM;int IcsLength(char x,char y) int m=M-1; int n=N-1; int i,j;for(i=1;i=M;i+)ci0=0; for(i=1;i=N;i+) c0i=0; for(i=1;i=M;i+) for(j=1;j=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; return cmn; int Ics(int i,int j,char x)if(i=0|j=0)return 0;if(bij=1)Ics(i-1,j-1,x);printf(%cn,xi);else if(bij=2)Ics(i-1,j,x);else Ics(i,j-1,x);return 0;void main()char x=A,0,C,B,D,A,B; char y=0,B,D,C,A,B,A;int i,j;printf(长度为%dn,IcsLength(x,y);for(i=0;iM;i+)for(j=0;jN;j+) printf(%dt,cij);printf(n);for(i=0;iM;i+) for(j=0;jN;j+) printf(%dt,cij); printf(n);Ics(M-1,N-1,x);五、分析与讨论分析：（1） 建立子问题最优值的递归关系。用cij记录序列Xi和Yi的最长公共子序列的长度。其中，Xi=x1,x2,xi;Yi=y1,y2,.yj.当i=0或j=0时，空序列是Xi和Yi的最长公共子序列，故此时cij=0（2） 输出两个数组c和b。其中，cij 存储Xi和Yj的最长公共子序列的长度，bij记录cij的值是由哪一个子问题的解得到的，这在构造最长公共子序列时
人人文库> 全部分类> 应用文书 > 工作计划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论