如何使用python實(shí)現(xiàn)最長(zhǎng)公共子序列-創(chuàng)新互聯(lián)

這篇文章主要介紹如何使用python實(shí)現(xiàn)最長(zhǎng)公共子序列，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

在江州等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作定制開(kāi)發(fā),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站制作,網(wǎng)絡(luò)營(yíng)銷推廣,成都外貿(mào)網(wǎng)站建設(shè),江州網(wǎng)站建設(shè)費(fèi)用合理。

1.找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征

序列a共有m個(gè)元素，序列b共有n個(gè)元素，如果a[m-1]==b[n-1]，那么a[:m]和b[:n]的最長(zhǎng)公共子序列長(zhǎng)度就是a[:m-1]和b[:n-1]的最長(zhǎng)公共子序列長(zhǎng)度+1；如果a[m-1]!=b[n-1]，那么a[:m]和b[:n]的最長(zhǎng)公共子序列長(zhǎng)度就是MAX（a[:m-1]和b[:n]的最長(zhǎng)公共子序列長(zhǎng)度，a[:m]和b[:n-1]的最長(zhǎng)公共子序列長(zhǎng)度）。

2.遞歸定義最優(yōu)值

3.以自底向上大方式計(jì)算出最優(yōu)值

python代碼如下：

def lcs(a,b): 
  lena=len(a) 
  lenb=len(b) 
  c=[[0 for i in range(lenb+1)] for j in range(lena+1)] 
  flag=[[0 for i in range(lenb+1)] for j in range(lena+1)] 
  for i in range(lena): 
    for j in range(lenb): 
      if a[i]==b[j]: 
        c[i+1][j+1]=c[i][j]+1 
        flag[i+1][j+1]='ok' 
      elif c[i+1][j]>c[i][j+1]: 
        c[i+1][j+1]=c[i+1][j] 
        flag[i+1][j+1]='left' 
      else: 
        c[i+1][j+1]=c[i][j+1] 
        flag[i+1][j+1]='up' 
  return c,flag 
 
def printLcs(flag,a,i,j): 
  if i==0 or j==0: 
    return 
  if flag[i][j]=='ok': 
    printLcs(flag,a,i-1,j-1) 
    print(a[i-1],end='') 
  elif flag[i][j]=='left': 
    printLcs(flag,a,i,j-1) 
  else: 
    printLcs(flag,a,i-1,j) 
     
a='ABCBDAB' 
b='BDCABA' 
c,flag=lcs(a,b) 
for i in c: 
  print(i) 
print('') 
for j in flag: 
  print(j) 
print('') 
printLcs(flag,a,len(a),len(b)) 
print('')

運(yùn)行結(jié)果輸出如下：

4.根據(jù)計(jì)算最優(yōu)值得到的信息，構(gòu)造最優(yōu)解

上圖是運(yùn)行結(jié)果，第一個(gè)矩陣是計(jì)算公共子序列長(zhǎng)度的，可以看到最長(zhǎng)是4；第二個(gè)矩陣是構(gòu)造這個(gè)最優(yōu)解用的；最后輸出一個(gè)最優(yōu)解BCBA。

以上是“如何使用python實(shí)現(xiàn)最長(zhǎng)公共子序列”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

當(dāng)前標(biāo)題：如何使用python實(shí)現(xiàn)最長(zhǎng)公共子序列-創(chuàng)新互聯(lián)
網(wǎng)址分享：http://www.muchs.cn/article22/dhoicc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、靜態(tài)網(wǎng)站、網(wǎng)站導(dǎo)航、網(wǎng)站策劃、網(wǎng)頁(yè)設(shè)計(jì)公司、網(wǎng)站營(yíng)銷

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)