文件名称:1773
- 所属分类:
- 其他小程序
- 资源属性:
- [Windows] [Visual C] [源码]
- 上传时间:
- 2012-11-26
- 文件大小:
- 973kb
- 下载次数:
- 0次
- 提 供 者:
- rcpo****
- 相关连接:
- 无
- 下载说明:
- 别用迅雷下载,失败请重下,重下不扣分!
介绍说明--下载内容均来自于网络,请自行研究使用
求最长公共子系列的长度问题
若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X 的子序列是指存
在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k 有:zj=xij.例如,序列
Z={a,b,f,c}是序列X={a,b,c,f,b,c}的子序列,相应的递增下标序列为{1,2,4,6}。给定2
个序列X 和Y,当另一序列Z 既是X 的子序列又是Y 的子序列时,称Z 是序列X 和Y 的公共
子序列.给定2 个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X 和Y 的最长公共子序
列.
分析:
设系列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ,
则
(1)若xm=yn,则zk=xm=yn,且zk-1 是xm-1 和yn-1 的最长公共子序列.
(2)若xm≠yn 且zk≠xm,则Z 是xm-1 和Y 的最长公共子序列。
(3)若xm≠yn 且zk≠yn,则Z 是X 和yn-1 的最长公共子序列。
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序
列Xi 和Yj 的最长公共子序列的长度。其中, Xi={x1,x2,…,xi};Yj={y1,y2,…,yj}。当
i=0 或j=0 时,空序列是Xi 和Yj 的最长公共子序列。故此时C[i][j]=0。-err
若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X 的子序列是指存
在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k 有:zj=xij.例如,序列
Z={a,b,f,c}是序列X={a,b,c,f,b,c}的子序列,相应的递增下标序列为{1,2,4,6}。给定2
个序列X 和Y,当另一序列Z 既是X 的子序列又是Y 的子序列时,称Z 是序列X 和Y 的公共
子序列.给定2 个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X 和Y 的最长公共子序
列.
分析:
设系列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ,
则
(1)若xm=yn,则zk=xm=yn,且zk-1 是xm-1 和yn-1 的最长公共子序列.
(2)若xm≠yn 且zk≠xm,则Z 是xm-1 和Y 的最长公共子序列。
(3)若xm≠yn 且zk≠yn,则Z 是X 和yn-1 的最长公共子序列。
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序
列Xi 和Yj 的最长公共子序列的长度。其中, Xi={x1,x2,…,xi};Yj={y1,y2,…,yj}。当
i=0 或j=0 时,空序列是Xi 和Yj 的最长公共子序列。故此时C[i][j]=0。-err
(系统自动生成,下载前可以参看下载内容)
下载文件列表
1733.cpp
1733.dsp
1733.dsw
1733.ncb
1733.opt
1733.plg
Debug
.....\1115.exe
.....\1115.ilk
.....\1115.obj
.....\1115.pch
.....\1115.pdb
.....\1272.exe
.....\1272.ilk
.....\1272.obj
.....\1272.pch
.....\1272.pdb
.....\1337.exe
.....\1337.ilk
.....\1337.obj
.....\1337.pch
.....\1337.pdb
.....\1733.exe
.....\1733.ilk
.....\1733.obj
.....\1733.pch
.....\1733.pdb
.....\vc60.idb
.....\vc60.pdb
1733.dsp
1733.dsw
1733.ncb
1733.opt
1733.plg
Debug
.....\1115.exe
.....\1115.ilk
.....\1115.obj
.....\1115.pch
.....\1115.pdb
.....\1272.exe
.....\1272.ilk
.....\1272.obj
.....\1272.pch
.....\1272.pdb
.....\1337.exe
.....\1337.ilk
.....\1337.obj
.....\1337.pch
.....\1337.pdb
.....\1733.exe
.....\1733.ilk
.....\1733.obj
.....\1733.pch
.....\1733.pdb
.....\vc60.idb
.....\vc60.pdb