合工大程序設(shè)計(jì)藝術(shù)與方法實(shí)驗(yàn)四動(dòng)態(tài)規(guī)劃

1、程序設(shè)計(jì)藝術(shù)與方法課實(shí)驗(yàn)報(bào)*實(shí)驗(yàn)名棋驗(yàn)動(dòng)態(tài)規(guī)劃班學(xué)實(shí)驗(yàn)期2018612指導(dǎo)師徐本柱、實(shí)驗(yàn)?zāi)康暮鸵?1) 理解動(dòng)態(tài)規(guī)劃的基本思想、動(dòng)態(tài)規(guī)劃算法 的基本驟(2) 掌握動(dòng)態(tài)規(guī)劃算法實(shí)步驟動(dòng)態(tài)規(guī)劃三、實(shí)驗(yàn)項(xiàng)目摘要(1) 求兩個(gè)字符串的最長(zhǎng)公共子序列。X的一個(gè)子序列是相應(yīng)于X下標(biāo)序列1, 2,?, 的一個(gè)子序列，求解兩個(gè)序列的所有pea。b，可用的操作為，刪除串 aa中的某個(gè)字母換為另一個(gè)字母。對(duì)于b。中的子序列中長(zhǎng)度最大的，例如輸入：pear, peach輸出：(2) 給定兩個(gè)字符串 a和b，現(xiàn)將串a(chǎn)通過變換變?yōu)榇?個(gè)字符；在串 a的某個(gè)位置插入一個(gè)元素；將串 任意的串a(chǎn)和串b，輸出最少多少次能夠?qū)?/p>

2、串變?yōu)榇?思考：輸出變換的步驟(3)輸入一個(gè)矩陣，計(jì)算所有的子矩陣中和的最大值。 例如，輸入0 -2 -7 0 9 2 -6 2 -4 1-4 1-1 8 0 -2輸出為： 15四、實(shí)驗(yàn)結(jié)果與分析（源程序及相關(guān)說明）1.求兩個(gè)字符串的最長(zhǎng)公共子序列算法思想：通過動(dòng)態(tài)規(guī)劃求解： 選的子序列點(diǎn)，1表示遞歸選擇的公共子序列，Long表示選擇存儲(chǔ)著最大的長(zhǎng)度。seatstr1str1二維數(shù)組用于表示選擇的最長(zhǎng)公共子序列以及輸出時(shí)選擇的方向，其中（0，i-1），str2 （ 0，（0，i），str2 （ 0, j）j）的公共子序列,-1選擇str1 （ 0， i）， 的公共子序列的長(zhǎng)度，其中當(dāng)遞歸結(jié)束時(shí)

3、，0表示可str2 ( 0, j-1)Lon gm n就先將Long數(shù)組第一行第一列初始化為 同時(shí) Longij= Longi - 1j-1），如果選擇前者seatij=1中存儲(chǔ)的元素值，從m, n開始（束，就可以輸出字符串。0,方便計(jì)算，接著如果-1 + 1，如果 stri，否則 seatij=-1m,n分別為兩字符串的長(zhǎng)度）stri = strj, 貝U seatij為可選點(diǎn)，=strj ，貝y Longij=max;當(dāng)循環(huán)遍歷了兩個(gè)字符串后，就得出結(jié)論，在根據(jù) 先遞歸，后輸出對(duì)應(yīng)位置在字符串中的字符，遞歸結(jié)seatij=0(Lon gi- 1jLon gijseat#in elude s

4、tdafx.h#in clude#in cludevstri ng#in cludeviostreamusing n ames pace std;1表示選擇str1 （ 0， i-1 ）， str2 （ 0， j）的公共子序列,-1#defi ne MAXLEN 100int seatMAXLENMAXLEN;/ 選擇 str1 ( 0， i)， str2 ( 0， int Lon gMAXLENMAXLEN;/其中0表示可選的子序列點(diǎn)， j-1）的公共子序列 表示選擇str1 （ 0， i）， str2 （ 0，j）的公共子序列的長(zhǎng)度void LCSLe ngth(stri ng str1,

5、 stri ng str2, i nt m, int n) int i, j;for (i = 0; i v= m; i+)Lon gi0 = 0;for （j = 1; j v= n; j+）Lon g0j = 0；/第一行第一列不使用，方便計(jì)算for (i = 1; i v= m; i+)for (j = 1; j v= n; j+)if (str1i - 1 = str2j - 1)Lon gij = Longi - 1j - 1 + 1;seatij = 0;else if (Lo ngi - 1j = Lon gij - 1) seatij = 1; elseLon gij = Lo

6、n gij - 1;seatij = -1;/以str1為標(biāo)準(zhǔn)輸出bool Prin t(stri ng str1, i nt i, i nt j,i nt & m,i nt &n) if (i = 0 II j = 0) return true;if (seatij = 0)/先依次遞歸之后子序列，Prin t(str1, i - 1, j - 1, m, n);m = i;n = j;cout str1i - 1;return true;else if (seatij = 1)Prin t(str1, i - 1, j, m, n);elsePrin t(str1, i, j - 1, m

7、, n);void LCS()stri ng str1, str2;int m = 0, n = 0, i = 0, j = 0;cout str1;cout str2;i = str1en gth();j = str2.le ngth();之后再輸入該子序列符號(hào)，以保證輸入的正確性 endl; endl;Prin t(str1, i, j, m, n);int _tmai n(int argc, _TCHAR* argv) LCSLe ngth(str1, str2,i,j);cout 最長(zhǎng)子序列為： endl; Lon gm n en dl;system(” pause);LCS(); r

8、eturn 0;cout en dl;cout 最長(zhǎng)子序列長(zhǎng)度為:2. 字符串的變換:handle 表示操作，其中handle存儲(chǔ)的數(shù)1為刪除，4為相同跳至兩重for循環(huán)遍歷所有組合的點(diǎn)，如果否則,handleij = 4;str1字符串，表示操作的步驟。#in clude stdafx.h#in clude#in cludeusing n ames pace std;#define MAX 1000#in cludevstri ng#in clude vvector2為插入，3為替換，str1i = str2j，貝U Distanceij = Distancei - 1j - 1為對(duì)應(yīng)的行號(hào)

9、Distanee表示距離，handle開始的第一行第一列為5，如果str1i ! = str20 , handle為3，列同理；其中Distanee函數(shù)的作用Distancem-1n-1( mhan dleij = min val(Dista ncei - 1j + 1, Dista nceij - 1 + 1, Dista ncei - 1j - 1 + 1, Dista nceij); min val 是比較最大值，并返回最大值對(duì)應(yīng)的操作，1為刪除，2為插入，3為替換，當(dāng)循環(huán)結(jié)束時(shí)，在分別為兩字符串的長(zhǎng)度)中存儲(chǔ)著最少操作次數(shù)nL工亠丄 呂：-使用動(dòng)態(tài)規(guī)劃的思想: 定義兩個(gè)數(shù)組， 下一個(gè)字

10、符， 先初始化，令 或者列號(hào)。5為結(jié)束狀態(tài)。輸出步驟： 最后先遞歸，后操作，修改int han dleMAXMAX;const stri ng OP ERATOR_NAME4 = H刪除串a(chǎn)中的一個(gè)字符在串a(chǎn)插入一個(gè)元素將串a(chǎn)中的,H字母換為另一個(gè)字母;/比較最大值，并返回最大值對(duì)應(yīng)的操作，int min val( int x, i nt y, i nt z,i nt &d)1為刪除，2為插入，3為替換if (x y)if (x z)d = x;return 1; elsereturn 3;elseif (y z)d = y; return 2; elsereturn 3;void Prin

11、tHa ndle(i nt i,i nt j,stn ng &str1,stri ng str2) if (ha ndleij = 1)/ 刪除 cout OPERATOR NAME0 str1i endl;str1.erase(str1.beg in() + i);cout 當(dāng)前 a 字符串： str1 endl;Prin tHa ndle(i - 1, j, str1, str2);else if (han dleij = 2)/ 插入cout OP ERATOR_NAME1 str2j endl;str1.i nsert(str1.begi n() + i+1, str2j);cout

12、當(dāng)前 a 字符串： str1 endl;Prin tHa ndle(i, j - 1, str1, str2);else if (ha ndleij = 3)/ 替換cout OP ERATOR_NAME2 str1i OP ERATOR_NAME3 str2j en dl; str1.erase(str1.beg in() + i);str1.i nsert(str1.begi n() + i, str2j);cout 當(dāng)前 a 字符串： str1 str2.le ngth() if (str1i-1 != str2j)cout OP ERATOR_NAME0 str1i - 1 endl;

13、str1.erase(str1.begi n() + i - 1);cout 當(dāng)前 a 字符串： str1 0)Prin tHa ndle(i - 1, j, str1, str2); elseif (str1i != str2j-1)cout OP ERATOR_NAME1 str2j - 1 endl;str1.i nsert(str1.begi n() + i, str2j - 1);cout ” 當(dāng)前 a 字符串: str1 0)Prin tHa ndle(i, j - 1, str1, str2);/編輯距離函數(shù)，str1 str2為操作的字符串void OUTdista nce(s

14、tri ng str1, stri ng str2, i nt len thofstr1, i nt len thofstr2) int i, j;for (i - 0; ile nthofstr1; i+)if (str1i - str20)Dista ncei0 - i; han dlei0 - 5; elseDista ncei0 - i + 1; han dlei0 - 3;for (i - 0; ile nthofstr2; i+) if (str10 - str2i) Dista nce0i - i; han dle0i - 5; elseDista nce0i - i + 1;

15、han dle0i - 3;for (i = 1; ile nthofstrl; i+)for (j - 1; jle nthofstr2; j+)/如果對(duì)應(yīng)的字符相等，原問題交給子問題處理，即不用任何操作if (str1i - str2j)Distanceij - Distanced 1j 1;han dleij = 4; else/否則的話，對(duì)左、右、左上角的值進(jìn)行求最小值han dleij = min val(Dista ncei - 1j + 1, Dista nceij - 1 + 1, Dista ncei - 1j - 1 + 1, Dista nceij);cout 輸出步驟：

16、 endl;Prin tHa ndle(le nthofstr1-1, le nthofstr2-1, str1, str2); cout 最少的操作次數(shù)是： Dista ncele nthofstr1 - 1le nthofstr2 - 1 endl;int STRCha ng()stri ng str1, str2;cout 輸入第一個(gè)字符串: str1;cout 輸入第二個(gè)字符串: str2;int len thofstr1 = str1.le ngth();int len thofstr2 = str2en gth();OUTdista nce(str1, str2,le nthofs

17、tr1,le nthofstr2); system(” pause);return 0;int _tmai n(int argc, _TCHAR* argv) STRCha ng();return 0;:疋丄.冗一 t亠上 .* r冊(cè)i說門丁J- It二J壬 H N 干 *4 T y 訂半； ：二：f亠上 i A二門 );=,n三二亍壬疋亠耳 I寧ii汁4 彳士L-10?壬曲j4-1 -J Pl PF亠冷小L h 三刖匚： :捋工口 -于豐！ : : -kn-? r ： iP? i ! - rt二寧七沱丄斗i寧討J 工： 1 上丄：止 Y：lk 1 Ir l、：二 2 止 rI 丄3：j t廿

18、二】匚：:riP: i 1廠門1 J J1.4.亠_亠_1.亠.L:_LiJ 亠 丄J.亠，七 L, , X忡一工一豐:i ：-1 :- k i I t ； 1 r： J 陥二亠唱*: : (T, /； o 匚 4:IJ_ A二匕戶F二3.計(jì)算所有的子矩陣中和的最大值使用動(dòng)態(tài)規(guī)劃:使用一個(gè)二維數(shù)組，其中numij存儲(chǔ)矩陣i*j的元素和。num存儲(chǔ)的方法旦入后就得到了矩陣元素和的二維數(shù)組。使用三個(gè)變量i,j,k來遍歷，一個(gè)矩陣大小是再使j從每一個(gè)i到M，遍歷所有行可能。再考慮列方向，直接在每一種i,j組合下，進(jìn)行樣就等于是把所有子矩陣的情形給遍歷完了。疋：numijM*N+= numi - 1j;循環(huán)輸 的，那么使i從0到M，0到N的遍歷，那么這每次遍歷的過程是：從i，j點(diǎn)開始，temp =numjk-numi- 1k，表示行為i-1到j(luò)，列為1到k的矩陣的值，num max = max (num max , 0) +Maxtemp表示i-1到j(luò)，列為1到k的矩陣中從k向上最大的子矩陣元素和，max (n ummax , Max)表示最大的子矩陣和，當(dāng)遍歷結(jié)束，就可以求出最大舉證和。思考：本算法可以求出100*100的矩陣# nclude stdafx.h #in clude #in clude #in cludevstri