实验四动态规划算法

实验四动态规划算法实验四动态规划算法一、实验目的与要求1、熟悉最长公共子序列问题的算法；2、初步掌握动态规划算法；二、实验题若给定序列X={x1,x2，…,xm}，贝9另一序列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的公共子序列。给定...

实验四动态规划算法一、实验目的与要求1、熟悉最长公共子序列问题的算法；2、初步掌握动态规划算法；二、实验题若给定序列X={x1,x2，…,xm}，贝9另一序列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,x2xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。三、实验提示include"stdlib.h"#include"string.h"voidLCSLength(char*x,char*y,intm,intn,int**c,int**b){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;}}}voidLCS(inti,intj,char*x,int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);printf("%c",x[i]);}elseif(b[i][j]==2)LCS(i-1,j,x,b);}实现思路：elseLCS(i,j-1,x,b);设序列X={xl,x2,…,xm}和Y={yl,y2,…,yn}的最长公共子序列为Z={zl,z2,…，zk}，贝(1)若xm二yn，则zk=xm=yn，且zkT是xmT和ynT的最长公共子序列。⑵若xmMyn且zkMxm，则Z是xmT和Y的最长公共子序列。⑶若xmMyn且zkMyn，则Z是X和ynT的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。实验代码：#include"stdafx.h"#include#include#include#includeusingnamespacestd;#defineN105intdp[N+1][N+1];charstr1[N],str2[N];intmaxx(inta,intb){if(a>b)returna;returnb;}intLCSL(intlen1,intlen2){inti,j;intlen=maxx(len1,len2);for(i=0;i<=len;i++){dp[i][0]=0;dp[0][i]=0;}for(i=1;i<=len1;i++)for(j=1;j<=len2;j++){if(str1[i-1]==str2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=maxx(dp[i-1][j],dp[i][j-1])}}returndp[len1][len2];}voidLCS(inti,intj){if(i==-1||j==-1)return;if(str1[i]==str2[j]){LCS(i-1,j-1);printf("%c",str1[i]);}elseif(dp[i-1][j]>dp[i][j-1])LCS(i-1,j);elseLCS(i,j-1);}intmain(){while(cin>>str1>>str2){intlen1=strlen(str1);intlen2=strlen(str2);cout<

                    本文档为【实验四 动态规划算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

你可能还喜欢

最新资料

资料动态

专题动态

酷酷龙

暂无简介~

格式：doc

大小：12KB

软件：Word

页数：4

分类：高中语文

上传时间：2022-12-28

浏览量：3

热点搜索

危化品安全管理判断题推销与谈判复习题目圈一圈，算一算_表内乘法和表内除法（二）优秀课件春节汤臣倍健系列的促销方案 2020年南京市鼓楼区五年级数学下册期末试卷含答案加强投资者教育工作铸造资本市场发展基石中信建投证券ppt课件管理学基础案例分析机动车检测站检测数据分析社区入户线路预案出口货物收汇申报表如何进行英文学术论文写作越南落地签证填写模板安全技术交底范本全套手足口病防治知识危化品安全管理判断题推销与谈判复习题目圈一圈，算一算_表内乘法和表内除法（二）优秀课件春节汤臣倍健系列的促销方案 2020年南京市鼓楼区五年级数学下册期末试卷含答案加强投资者教育工作铸造资本市场发展基石中信建投证券ppt课件管理学基础案例分析机动车检测站检测数据分析社区入户线路预案出口货物收汇申报表如何进行英文学术论文写作越南落地签证填写模板安全技术交底范本全套手足口病防治知识

实验四 动态规划算法

你可能还喜欢

实验四动态规划算法