问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501
你好,欢迎来到懂视!登录注册
当前位置: 首页 - 正文

最长 公共子序列问题(算法分析 C++)

发布网友 发布时间:2022-04-18 06:11

我来回答

1个回答

热心网友 时间:2022-04-18 07:40

#include <iostream>
#include <string>
using namespace std;
//主函数
int main()
{
int m,n;
char *x,*y;
int **b,**c;
void LCSLength(int m,int n,char *y,char *x,int **c,int **b);
void LCS(int i,int j,char *x,int**b);

cout<<"请输入两个序列的长度:"<<endl;
cin>>m>>n;
x=new char[m];
y=new char[n];
cout<<"请输入两个序列:"<<endl;
cin>>x>>y;
b=new int *[m + 1]; // 注意这里,原式没有+1
for (int i=0;i<=m;i++)
b[i]=new int[n + 1]; // 注意这里,原式没有+1
c=new int *[m + 1];
for (int j=0;j<=m;j++)
c[j]=new int[n + 1]; // 注意这里,原式没有+1
LCSLength(m,n,x,y,c,b);
cout<<"最长公共子序列的元素个数为"<<c[m][n]<<endl;
cout<<"该序列为:";
LCS(m,n,x,b); //注意后面的内容是清理,暂时先跳过去,你先搞定主程序先
/* delete []x;
delete []y;
for(int k=0;k<=m;k++)
delete []b[k];
delete []b;
for(int h=0;h<=m;h++)
delete []c[h];
delete []c;
*/
return 0;
}
//计算最优值
void LCSLength(int m,int n,char *y,char *x,int **c,int **b)
{
int i,j;
for(i=1;i<=m;i++)c[i][0]=0;
for(j=0;j<=n;j++)c[0][j]=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;}
else if(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;}
}
}
//构造最长公共子序列
void LCS(int i,int j,char *x,int**b)
{
if(i==0||j==0)return;
if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<<x[i];}
else if(b[i][j]==2)LCS(i-1,j,x,b);
else LCS(i,j-1,x,b);
}
声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。
E-MAIL:11247931@qq.com
网上到底有没有钢《铁侠侠3》的高清完整版呀? 有木有下载[钢铁侠3BD1280真正高清收藏版][161电影网种子的网址_百度知 ... 苏州甪直怎样坐车去上海虹桥?要快的! 从吴江自驾去上海虹桥机场T2航站楼怎么走?大约要多久?有停车场不?第一... 从甪直开车到上海虹桥机场T1航站楼怎么走? 甪直到虹桥机场多长时间? 柴油暖风机多少钱一台_柴油暖风机什么牌子好 国务院关于加快发展现代保险服务业的若干意见 国发2019 29号_百度知 ... 八万的那个夏天是什么意思? 北京BW007有什么安全配置 牙膏弄黑色衣服上能洗掉么 室内设计办公室效果图用什么软件 室内设计涉及到哪些软件? 桌面一刷新,图标位置就改变了,怎么回事? 桌面图标每次刷新后的位置就会变了是怎么回事? 阿凡达的主编是谁 阿凡达由丹尼斯·勒翰的什么小说改编的 为什么卡梅隆在拍《阿凡达》的时候,不选一个好的剧本 阿凡达是根据什么书写的呢 阿凡达到底是真人还是动画的 阿凡达的由来 阿凡达是谁写的? 介绍阿凡达电影作者 ? 詹姆斯卡梅隆花了多长时间筹划《阿凡达》? 电影阿凡达改编自哪本书 阿凡达的创作背景 阿凡达 的原著是? 我想改QQ密码怎么改 手机QQ空间 新浪微博诈骗信息 在新浪微博被骗了怎么办? 权力的游戏第五季 萨莎史塔克死了没 鲨海逃生最后谁死了? NBA火箭主帅麦克海尔之女23岁美少女萨沙死因 在《进击的巨人》中,动漫中萨沙死了艾伦为什么要笑? 冥王神话结局演了什么?亚伦、天马、萨莎怎么样了?两个问题都回答! 麦克海尔女儿怎么死的 进击的巨人莎夏第几集死的 《圣斗士星矢冥王神话OVA》后天马,亚伦,萨莎,还有潘多拉的最终结局是什么? 权力的游戏第五季 萨莎史塔克和席恩跳下悬崖,怎么没死的? 行尸走肉第七季14集萨沙死了吗 2012中萨沙是怎么死的? 行尸走肉第七季第16集最后谁死了 越狱第四季中,男主角最后是怎么死的? 行尸走肉第五季马丁不是被泰尔西打死了吗 WIFI无线上网怎么用 手机WIFI上网是怎么回事?要怎样才能用WIFI上网,详细点 帮我写一个网页计算器公式代码 求一个网站计数器代码,要通用的HTML代码(分数不是问题,在线等)_百度... 用HTML代码编写计算器,,使用计算时,,若存在小数点就会出错,,例如78.1... html计算器 --这段代码错哪了???
  • 焦点

最新推荐

猜你喜欢

热门推荐