合工大程序設計藝術與方法實驗四動態(tài)規(guī)劃

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

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

3、，0表示可str2 ( 0, j-1)Lon gm n就先將Long數(shù)組第一行第一列初始化為 同時 Longij= Longi - 1j-1），如果選擇前者seatij=1中存儲的元素值，從m, n開始（束，就可以輸出字符串。0,方便計算，接著如果-1 + 1，如果 stri，否則 seatij=-1m,n分別為兩字符串的長度）stri = strj, 貝U seatij為可選點，=strj ，貝y Longij=max;當循環(huán)遍歷了兩個字符串后，就得出結論，在根據(jù) 先遞歸，后輸出對應位置在字符串中的字符，遞歸結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表示可選的子序列點， j-1）的公共子序列 表示選擇str1 （ 0， i）， str2 （ 0，j）的公共子序列的長度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；/第一行第一列不使用，方便計算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為標準輸出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();之后再輸入該子序列符號，以保證輸入的正確性 endl; endl;Prin t(str1, i, j, m, n);int _tmai n(int argc, _TCHAR* argv) LCSLe ngth(str1, str2,i,j);cout 最長子序列為： endl; Lon gm n en dl;system(” pause);LCS(); r

8、eturn 0;cout en dl;cout 最長子序列長度為:2. 字符串的變換:handle 表示操作，其中handle存儲的數(shù)1為刪除，4為相同跳至兩重for循環(huá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為對應的行號

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 是比較最大值，并返回最大值對應的操作，1為刪除，2為插入，3為替換，當循環(huán)結束時，在分別為兩字符串的長度)中存儲著最少操作次數(shù)nL工亠丄 呂：-使用動態(tài)規(guī)劃的思想: 定義兩個數(shù)組， 下一個字

10、符， 先初始化，令 或者列號。5為結束狀態(tài)。輸出步驟： 最后先遞歸，后操作，修改int han dleMAXMAX;const stri ng OP ERATOR_NAME4 = H刪除串a(chǎn)中的一個字符在串a(chǎn)插入一個元素將串a(chǎn)中的,H字母換為另一個字母;/比較最大值，并返回最大值對應的操作，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 當前 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、當前 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 當前 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 當前 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 ” 當前 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+)/如果對應的字符相等，原問題交給子問題處理，即不用任何操作if (str1i - str2j)Distanceij - Distanced 1j 1;han dleij = 4; else/否則的話，對左、右、左上角的值進行求最小值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 輸入第一個字符串: str1;cout 輸入第二個字符串: 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冊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.計算所有的子矩陣中和的最大值使用動態(tài)規(guī)劃:使用一個二維數(shù)組，其中numij存儲矩陣i*j的元素和。num存儲的方法旦入后就得到了矩陣元素和的二維數(shù)組。使用三個變量i,j,k來遍歷，一個矩陣大小是再使j從每一個i到M，遍歷所有行可能。再考慮列方向，直接在每一種i,j組合下，進行樣就等于是把所有子矩陣的情形給遍歷完了。疋：numijM*N+= numi - 1j;循環(huán)輸 的，那么使i從0到M，0到N的遍歷，那么這每次遍歷的過程是：從i，j點開始，temp =numjk-numi- 1k，表示行為i-1到j，列為1到k的矩陣的值，num max = max (num max , 0) +Maxtemp表示i-1到j，列為1到k的矩陣中從k向上最大的子矩陣元素和，max (n ummax , Max)表示最大的子矩陣和，當遍歷結束，就可以求出最大舉證和。思考：本算法可以求出100*100的矩陣# nclude stdafx.h #in clude #in clude #in cludevstri