实验二 动态规划算法
11页1、实验二 动态规划算法基本题一:最长公共子序列问题一、实验目的与要求1、熟悉最长公共子序列问题的算法;2、初步掌握动态规划算法;二、实验题 若给定序列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的最长公共子序列。 三(1)实验源代码:/最长公共子序问题:/问题描述: 若给定序列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是序列
2、X和Y的公共子序列。/给定2个序列X=x1,x2,xm和Y=y1,y2,yn,找出X和Y的最长公共子序列。 #includeusing namespace std;#define max 1000/注意:这里使用的char数组,可以按字符输出,若改为string类型,/执行printf(%c,Am-1)就会报错; char A100,B100; /输入的两个串a和b/这里定义全局变量可以不赋值0,因为全局变量自动赋值0; int cmaxmax; /记录最长公共子序的长度; int bmaxmax; /记录状态号; void LCS(int m,int n)if(m=0|n=0)return;else if(bmn=1)LCS(m-1,n-1);printf(%c,Am-1); else if(bmn=2)m=m-1;LCS(m,n);else if(bmn=3)n=n-1;LCS(m,n);void LCS_length(int m,int n)for(int i=1;i=m;i+)for(int j=1;j=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;b
3、ij=3;int main()printf(请输入两个待测的字符串:n);scanf(%s,&A); scanf(%s,&B);int m=strlen(A); /m为A串长度; int n=strlen(B); /n为B串长度; LCS_length(m,n);printf(其最长公共子序的长度为:%dn,cmn);printf(其最长公共子序为:);LCS(m,n);return 0;(2)运行结果为:(3)算法思路:最长公共子序列的结构有如下表示:设序列X=和Y=的一个最长公共子序列Z=,则:1. 若xm=yn,则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列;2. 若xmyn且zkxm ,则Z是Xm-1和Y的最长公共子序列;3. 若xmyn且zkyn,则Z是X和Yn-1的最长公共子序列。其中Xm-1=,Yn-1=,Zk-1=。基本题二:最大字段和问题一、实验目的与要求1、熟悉最长最大字段和问题的算法;2、进一步掌握动态规划算法;二、实验题若给定n个整数组成的序列a1,a2,a3,an,求该序列形如aiai1an的最大值。三,实验源代码:#include#defi
《实验二 动态规划算法》由会员壹****1分享,可在线阅读,更多相关《实验二 动态规划算法》请在金锄头文库上搜索。
初中英语单项选择100篇.doc
卫星电视广播地面接收设备生产许可证换(发)证实施细则.docx
学习《全面从严治党面对面》的体会.doc
市场监管总局、商务部关于发挥网络餐饮平台引领带动作用有效防范外卖食品浪费的指导意见
《正确认识好奇心理》教案.doc
2023年军训徒步拉练心得体会.docx
岩土工程试卷.doc
最新高一数学人教A版必修1学业分层测评16 对数的运算 Word版含解析
股权质押担保合同样本(8篇)
生理学模拟题
安全员的职责范围范本(四篇).doc
倒装句高考试题.doc
安全生产投入保障制度电子版(五篇).doc
计算机网络技术的应用探索.doc
《2、山雨》教学设计和反思.doc
全日制劳动合同书经典版(8篇)
化粪池沉井施工方案(DOC 10页)
煤矿安全年度生产工作总结
第四单元塞北江南葡萄沟.doc
中国著名电影表演艺术家陈强
2023-02-19 5页
2023-05-06 1页
2023-10-09 5页
2022-12-17 3页
2022-10-11 6页
2022-12-12 2页
2023-12-06 6页
2023-09-29 6页
2023-08-19 21页
2022-10-11 6页