国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

動態規劃之最長公共子序列

2019-11-06 07:45:41
字體:
來源:轉載
供稿:網友

目錄

最長公共子序列簡介舉例說明并分析代碼塊測試結果

最長公共子序列簡介

一個給定序列的子序列是在該序列中刪去若干元素后得到的序列,確切的說,若給定序列X={x0,x1…,xm-1}, 則另一序列Z={z0,z1,…,zk-1},X的子序列是指存在一個嚴格的下標序列{i0,i1…,ik-1},使得對于所有的j=0,1,…,k-1有Zj=Xij。例如序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相應的遞增下標序列維{1,2,4,6}。

最長公共子序列問題如何分解成子問題,設A=“a0,a1,…,am-1”,B=“b0,b1,…,bm-1”,并Z=“z0,z1,…,zk-1”為它們的最長公共子序列。求解最長公共子序列長度。


舉例說明并分析

窮舉搜索法是最容易想到的方法,對X的所有子序列,檢查它是否也是Y的子序列,從而確定它是否為X和Y的公共子序列,并且在檢查過程中記錄最長的公共子序列,X的所有子序列都檢查后即可求出X和Y的最長公共子序列,x的每個子序列相應與下標集{0,1,2,……,m-1}的一個子集,因此共有2的m次方個不同子序列,從而窮舉法需要指數時間。 事實上,最長公共子序列問題具有最優子結構性質。

(1) 如果am-1=bn-1,則zk-1=am-1=bn-1,且“z0,z1,…,zk-2”是“a0,a1,…,am-2”和“b0,b1,…,bn-2”的一個最長公共子序列;

(2) 如果am-1!=bn-1,則若zk-1!=am-1,蘊涵“z0,z1,…,zk-1”是“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一個最長公共子序列;

(3) 如果am-1!=bn-1,則若zk-1!=bn-1,蘊涵“z0,z1,…,zk-1”是“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一個最長公共子序列。

這樣,在找A和B的公共子序列時,如有am-1=bn-1,則進一步解決一個子問題,找“a0,a1,…,am-2”和“b0,b1,…,bm-2”的一個最長公共子序列;如果am-1!=bn-1,則要解決兩個子問題,找出“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一個最長公共子序列和找出“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一個最長公共子序列,再取兩者中較長者作為A和B的最長公共子序列。

這里寫圖片描述


首先建立子問題最優值的遞歸關系。用c[i][j]記錄序列Xi和Yj的最長公共子序列的長度,b[i][j]記錄c[i][j]的值是由哪一個子問題的解得到的。 動態規劃是自底向上進行遞歸的 那么在計算c[i][j]之前,c[i-1][j-1]和c[i-1][j]以及c[i][j-1]都應該知道

這里寫圖片描述


代碼塊

#include <stdio.h>#include<stdlib.h>#include <string.h>#define MAXLEN 100void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN]){ int i, j; for (i = 0; i <= m; i++) c[i][0] = 0; //單個序列的最長公共子序列為0 for (j = 1; j <= n; j++) c[0][j] = 0; //單個序列的最長公共子序列為0 for (i = 1; i <= m; i++) { for (j = 1; j <= n; j++) { if (x[i-1] == y[j-1])//因為x序列和y序列的坐標都是從0開始的,所有最后一個下標為i-1,j-1; { 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]; //滿足m-1!=n-1且k-1!=m-1情況從X{0,1,2...,m-2}和Y{0,1,2..,n-1}開始尋找 b[i][j] = 2; } else { c[i][j] = c[i][j - 1]; //滿足m-1!=n-1且k-1!=n-1情況從X{0,1,2...,m-1}和Y{0,1,2..,n-2}開始尋找 b[i][j] = 3; } } }}void PRintLCS(int b[][MAXLEN], char *x, int i, int j){ if (i == 0 || j == 0) //遞歸到兩個數組中任意一個的下標為0時結束 return; if (b[i][j] == 1) { PrintLCS(b, x, i - 1, j - 1); printf("%c ", x[i - 1]); } else if (b[i][j] == 2) PrintLCS(b, x, i - 1, j); else PrintLCS(b, x, i, j - 1);}int main(int argc, char **argv){ char x[MAXLEN] ; char y[MAXLEN] ; printf("請輸入較長序列的數據:/n"); scanf("%s", x); getchar(); printf("請輸入較短序列的數據:/n"); scanf("%s", y); int b[MAXLEN][MAXLEN]; int c[MAXLEN][MAXLEN]; int m, n; m = strlen(x); n = strlen(y); LCSLength(x, y, m, n, c, b); printf("最長公共子序列是:/n"); PrintLCS(b, x, m, n);//x數組必須是序列較長的數組 printf("/n長度是%d", c[m][n]); system("pause"); return 0;}

測試結果

這里寫圖片描述


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 中江县| 瑞安市| 灵宝市| 黎城县| 宣化县| 青海省| 宣汉县| 漠河县| 宽甸| 普陀区| 梁平县| 当阳市| 大渡口区| 湟源县| 乐都县| 武宣县| 甘孜| 南雄市| 大悟县| 河池市| 亚东县| 黑河市| 沙雅县| 伊金霍洛旗| 石林| 宾川县| 五常市| 林周县| 延长县| 嘉定区| 克什克腾旗| 思南县| 团风县| 息烽县| 中宁县| 吴忠市| 大厂| 鄱阳县| 若尔盖县| 石嘴山市| 民权县|