收藏 分销(赏)

最长公共子序列.doc

上传人:a199****6536 文档编号:1989011 上传时间:2024-05-13 格式:DOC 页数:6 大小:20.20KB
下载 相关 举报
最长公共子序列.doc_第1页
第1页 / 共6页
最长公共子序列.doc_第2页
第2页 / 共6页
最长公共子序列.doc_第3页
第3页 / 共6页
最长公共子序列.doc_第4页
第4页 / 共6页
最长公共子序列.doc_第5页
第5页 / 共6页
点击查看更多>>
资源描述

1、动态规划一、 问题描述用动态规划法求两个字符串A=xzyzzyx和B=zxyyzxz的最长公共子序列二、 算法分析(1)、若xm=yn,则zk=xm=yn,且Zk-1是Xm-1和Yn-1的最长公共自序列;(2)、若xmyn,且zkxm,则Zk是Xm-1和Yn的最长公共自序列;(3)、若xmyn,且zkyn,则Zk是Xm和Yn-1的最长公共自序列;设L(m,n)表示序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列的长度L表示已经决策的长度S表示每个决策的状态L(0,0)=L(0,j)=0 1im, 1jn L(i-1,j-1)+1 xi=yi,i1,j1L(i,j)= maxL(i

2、,j-1),(L(i-1,j) xiyi,i1,j1 1 xi=yiS(i,j)= 2 xiyi 且L(i,j-1)L(i-1,j) 3 xiyi 且L(i,j-1) L(i-1,j) xzyzzyx00000000z00111111x01111222y01122222y01122333z01122334x01123334z01223344长度矩阵L三、 源代码#include #include using namespace std; int main() string str1 = xzyzzyx; string str2 = zxyyzxz; int x_len = str1.lengt

3、h(); int y_len = str2.length(); int arr5050 =0,0; int i = 0; int j = 0; for(i = 1; i = x_len; i+) for(j = 1; j = arri - 1j) arrij = arrij - 1; else arrij = arri -1j; for(i = 0 ; i = x_len; i+) for( j = 0; j = y_len; j+) cout arrij ; cout = 1 & j = 1;) if(str1i - 1 = str2j - 1) cout str1i - 1 arri - 1j) j-; else i-; cout endl; return 0;

展开阅读全文
收益排行: 01、路***(¥15400+),
02、曲****(¥15300+),
03、wei****016(¥13200+),
04、大***流(¥12600+),
05、Fis****915(¥4200+),
06、h****i(¥4100+),
07、Q**(¥3400+),
08、自******点(¥2400+),
09、h*****x(¥1400+),
10、c****e(¥1100+),
11、be*****ha(¥800+),
12、13********8(¥800+)。
相似文档                                   自信AI助手自信AI助手
百度文库年卡

猜你喜欢                                   自信AI导航自信AI导航
搜索标签

当前位置:首页 > 包罗万象 > 大杂烩

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        获赠5币

©2010-2024 宁波自信网络信息技术有限公司  版权所有

客服电话:4008-655-100  投诉/维权电话:4009-655-100

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :gzh.png    weibo.png    LOFTER.png 

客服