算法設(shè)計(jì)與分析實(shí)驗(yàn)指導(dǎo)書(編輯修改稿)
2024-08-31 09:51 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 子結(jié)構(gòu)性質(zhì)。設(shè)X = { x1 , ... , xm }，Y = { y1 , ... , yn }，及它們的最長(zhǎng)子序列Z = { z1 , ... , zk }，則：（1）若xm = yn，則zk = xm = yn，且Z[k1]是X[m1]和Y[n1]的最長(zhǎng)公共子序列（2）若xm != yn，且zk != xm ,則Z是X[m1]和Y的最長(zhǎng)公共子序列（3）若xm != yn, 且zk != yn ,則Z是Y[n1]和X的最長(zhǎng)公共子序列由性質(zhì)導(dǎo)出子問(wèn)題的遞歸結(jié)構(gòu)當(dāng) i = 0 , j = 0 時(shí), c[i][j] = 0當(dāng) i , j 0 。 xi = yi 時(shí), c[i][j] = c[i1][j1] + 1當(dāng) i , j 0 。 xi != yi 時(shí), c[i][j] = max { c[i][j1], c[i1][j] }2．參考代碼include iostreamusing namespace std。define max 100int L[max][max]。 //長(zhǎng)度矩陣int S[max][max]。 //狀態(tài)矩陣int CommonOrder(int m, int n, char x[], char y[], char z[]){ int i, j, k。 for (j=0。 j=n。 j++) L[0][j]=0。 // 初始化第0行 for (i=0。 i=m。 i++) L[i][0]=0。 // 初始化第0列 for (i=1。 i=m。 i++) for (j=1。 j=n。 j++) if (x[i]==y[j]) { L[i][j]=L[i1][j1]+1。 S[i][j]=1。 } else if(L[i][j1]=L[i1][j]) { L[i][j]=L[i][j1]。 S[i][j]=2。 } else { L[i][j]=L[i1][j]。 S[i][j]=3。 } i=m。 j=n。 k=L[m][n]。 while (i0 amp。amp。 j0) { if (S[i][j]==1) { z[k]=x[i]。 k。 i。
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1