最長(zhǎng)公共子序列問(wèn)題

1、實(shí)驗(yàn)三最長(zhǎng)公共子序列問(wèn)題實(shí)驗(yàn)環(huán)境本實(shí)驗(yàn)采納java語(yǔ)言編寫(xiě)實(shí)現(xiàn)，環(huán)境：，編譯器：eclipse實(shí)驗(yàn)?zāi)康慕?jīng)過(guò)最長(zhǎng)公共子序列問(wèn)題，穩(wěn)固并詳盡剖析動(dòng)向規(guī)劃思想和解題步驟。設(shè)計(jì)思路最長(zhǎng)公共子序列的定義為：設(shè)有兩個(gè)序列S11.m和S21.n，需要找尋它們之間的一個(gè)最長(zhǎng)公共子序列。比如，假設(shè)有兩個(gè)序列：S1：INTHEBEGINNINGS2：ALLTHINGSARELOST則S1和S2的一個(gè)最長(zhǎng)公共子序列為T(mén)HING。又比方：S1：ABCBDABS2：BDCABA則它們的一個(gè)最長(zhǎng)公共子序列為BCBA。這里需要注意的是，一個(gè)子序列不必定一定是連續(xù)的，即中間可被其余字符分開(kāi)，單它們的次序一定是正確的。此外，最

2、長(zhǎng)公共子序列不必定只有一個(gè)，而我們需要找尋的是此中一個(gè)。自然，假如要求子序列里面的元素一定連成一片也是能夠的。實(shí)際上，連成一片的版本比這里實(shí)現(xiàn)的更簡(jiǎn)單。過(guò)程我們能夠經(jīng)過(guò)蠻力策略解決這個(gè)問(wèn)題，步驟以下：檢查S11.m里面每一個(gè)子序列。看看其能否也是S21.n里的子序列。在每一步記錄目前找到的子序列里面最長(zhǎng)的子序列。這類(lèi)方法的效率十分低下。所以本實(shí)驗(yàn)采納動(dòng)向規(guī)劃的方法實(shí)現(xiàn)該算法。利用動(dòng)向規(guī)劃找尋最長(zhǎng)公共子序列步驟以下：找尋最長(zhǎng)公共子序列的長(zhǎng)度。擴(kuò)展找尋長(zhǎng)度的算法來(lái)獲得最長(zhǎng)公共子序列。策略：考慮序列S1和S2的前綴序列。設(shè)ci，j=|LCS(S11.i,S21.j)|，則有cm，n=|LCS(S1，

3、S2)|所以有ci1，j1+1，如要S1i=S2jci，j=maxci-1，j，ci，j-1，假如S1iS2j而后回溯輸出最長(zhǎng)公共子序列過(guò)程：實(shí)現(xiàn)源代碼packagelcsimple;publicclassLCSImplem斷點(diǎn)調(diào)試及代碼剖析第一在main方法里定義兩個(gè)字符串，如：對(duì)這兩個(gè)字符串，使它們的第一個(gè)字符為空，即初始化以后的c的第一行第一列，之所以要空出，是因?yàn)閏代表的是兩個(gè)字符串?dāng)?shù)組多少個(gè)，0的意思就是某個(gè)字符串的長(zhǎng)度為0。而后將這兩個(gè)字符串切割為char型數(shù)組：接下來(lái)就調(diào)用getLength方法計(jì)算出決定搜尋方向的數(shù)組，傳到該方法的兩個(gè)數(shù)組參數(shù)stringArr1和stringA

4、rr2的值能夠看到而后定義兩個(gè)二維數(shù)組b，c，大小為*，用于接受結(jié)果矩陣。接著遍歷每一個(gè)stringArr1的值，與stringArr2的每一個(gè)值做比較：循環(huán)內(nèi)的第一層判斷，就是當(dāng)目前字符般配的時(shí)候，cij最為前綴序列為后邊的般配計(jì)算使用，將目前值賦值為1，bij用于保留般配結(jié)果記為1：把下邊的兩個(gè)判斷作為第二層判斷，即當(dāng)目前字符不般配的時(shí)候?qū)ij做計(jì)算，cij就是該值在矩陣中上面一個(gè)數(shù)和左側(cè)一個(gè)數(shù)中較大的值：這些判斷就是對(duì)該矩陣值的計(jì)算，c矩陣：可是這個(gè)方法返回的是b矩陣，b矩陣在目前地點(diǎn)在字符般配時(shí)的值為1，不般配時(shí)，就對(duì)c矩陣做出比較，該值在矩陣中左側(cè)的數(shù)值大于上面的數(shù)值時(shí)，b矩陣在目

5、前地點(diǎn)在字符般配時(shí)的值為0，反之記為-1。所以，計(jì)算返回b矩陣，輸出b矩陣獲得：最后就是對(duì)結(jié)果的輸出，對(duì)b矩陣調(diào)用Display方法：當(dāng)目前值為1時(shí)，說(shuō)明字符般配成功，再對(duì)左上方的值進(jìn)行比較；當(dāng)目前值為0時(shí)，說(shuō)明左側(cè)的值大于上面的值，采納遞歸法，再對(duì)上面的值進(jìn)行比較；當(dāng)目前值為-1時(shí)，對(duì)左側(cè)的值進(jìn)行比較。下邊是對(duì)的迭代：這個(gè)方法，就是對(duì)下邊矩陣方向的計(jì)算：最后輸出判斷中般配上的結(jié)果。算法剖析因?yàn)槊看握{(diào)用起碼向上或向左（或向上向左同時(shí)）挪動(dòng)一步，故最多調(diào)用(m*n)次就會(huì)碰到i=0或j=0的狀況，此時(shí)開(kāi)始返回。返回時(shí)與遞歸調(diào)用時(shí)方向相反，步數(shù)同樣，故算法時(shí)間復(fù)雜度為(m*n)。實(shí)驗(yàn)結(jié)果在main方法中輸入的字符串為：所以獲得結(jié)果：改變輸入的字符串測(cè)試：結(jié)果正確，實(shí)驗(yàn)結(jié)束。實(shí)驗(yàn)總結(jié)對(duì)最長(zhǎng)公共子序列的求解，其實(shí)是對(duì)動(dòng)向規(guī)劃思想的學(xué)習(xí)，這個(gè)實(shí)驗(yàn)實(shí)現(xiàn)的算法比前兩個(gè)實(shí)驗(yàn)實(shí)現(xiàn)的算法難度又有所提高，對(duì)字符串進(jìn)行頻頻遞歸時(shí)簡(jiǎn)單犯錯(cuò)，所以只好先