1、程序設(shè)計藝術(shù)與方法課程實驗報告實驗名稱實驗四 動態(tài)規(guī)劃姓 名班 級學(xué) 號實驗日期2018.6.12指導(dǎo)教師徐本柱成 績一、實驗?zāi)康暮鸵?1) 理解動態(tài)規(guī)劃的基本思想、動態(tài)規(guī)劃算法的基本步驟。(2) 掌握動態(tài)規(guī)劃算法實際步驟。二、實驗預(yù)習(xí)內(nèi)容動態(tài)規(guī)劃三、實驗項目摘要(1) 求兩個字符串的最長公共子序列。X 的一個子序列是相應(yīng)于X 下標(biāo)序列1, 2, , m的一個子序列，求解兩個序列的所有子序列中長度最大的，例如輸入：pear, peach 輸出：pea。(2) 給定兩個字符串a(chǎn) 和b，現(xiàn)將串a(chǎn) 通過變換變?yōu)榇産，可用的操作為，刪除串a(chǎn) 中的一個字符；在串a(chǎn) 的某個位置插入一個元素；將串a(chǎn) 中的

2、某個字母換為另一個字母。對于任意的串a(chǎn) 和串b，輸出最少多少次能夠?qū)⒋優(yōu)榇産。思考：輸出變換的步驟。(3) 輸入一個矩陣，計算所有的子矩陣中和的最大值。例如，輸入0 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2輸出為：15四、實驗結(jié)果與分析（源程序及相關(guān)說明）1. 求兩個字符串的最長公共子序列算法思想：通過動態(tài)規(guī)劃求解：seat二維數(shù)組用于表示選擇的最長公共子序列以及輸出時選擇的方向，其中0表示可選的子序列點(diǎn)，1表示遞歸選擇str1（0，i-1），str2（0，j)的公共子序列,-1選擇str1（0，i），str2（0，j-1)的公共子序列，Long表示選擇str1（0

3、，i），str2（0，j)的公共子序列的長度，其中當(dāng)遞歸結(jié)束時，Longmn就存儲著最大的長度。先將Long數(shù)組第一行第一列初始化為0，方便計算，接著如果stri = strj,則seatij為可選點(diǎn)，seatij=0，同時Longij = Longi - 1j - 1 + 1，如果stri ！= strj，則Longij=max（Longi - 1j Longij - 1），如果選擇前者seatij=1，否則seatij=-1；當(dāng)循環(huán)遍歷了兩個字符串后，就得出結(jié)論，在根據(jù)seat中存儲的元素值，從m，n開始（m,n分別為兩字符串的長度），先遞歸，后輸出對應(yīng)位置在字符串中的字符，遞歸結(jié)束，就可

4、以輸出字符串。#include stdafx.h#include#include#includeusing namespace std;#define MAXLEN 100int seatMAXLENMAXLEN;/其中0表示可選的子序列點(diǎn)，1表示選擇str1（0，i-1），str2（0，j)的公共子序列,-1選擇str1（0，i），str2（0，j-1)的公共子序列int LongMAXLENMAXLEN;/表示選擇str1（0，i），str2（0，j)的公共子序列的長度void LCSLength(string str1, string str2, int m, int n)int i,

5、j;for (i = 0; i = m; i+)Longi0 = 0;for (j = 1; j = n; j+)Long0j = 0;/第一行第一列不使用，方便計算for (i = 1; i = m; i+)for (j = 1; j = Longij - 1)Longij = Longi - 1j;seatij = 1;elseLongij = Longij - 1;seatij = -1;/以str1為標(biāo)準(zhǔn)輸出bool Print(string str1, int i, int j,int &m,int &n)if (i = 0 | j = 0)return true;if (seati

6、j = 0)/先依次遞歸之后子序列，之后再輸入該子序列符號，以保證輸入的正確性Print(str1, i - 1, j - 1, m, n);m = i;n = j;cout str1i - 1;return true;else if (seatij = 1)Print(str1, i - 1, j, m, n);elsePrint(str1, i, j - 1, m, n);void LCS()string str1, str2;int m = 0, n = 0, i = 0, j = 0;cout 輸入第一個字符串： str1;cout 輸入第二個字符串： str2;i = str1.le

7、ngth();j = str2.length();LCSLength(str1, str2,i,j);cout 最長子序列為： endl;Print(str1, i, j, m, n);cout endl;cout 最長子序列長度為： Longmn endl;system(pause);int _tmain(int argc, _TCHAR* argv)LCS();return 0;2. 字符串的變換：使用動態(tài)規(guī)劃的思想：定義兩個數(shù)組，Distance表示距離，handle表示操作，其中handle存儲的數(shù)1為刪除，2為插入，3為替換，4為相同跳到下一個字符，5為結(jié)束狀態(tài)。先初始化，令hand

8、le開始的第一行第一列為5，如果str1i ！= str20，handle為3，列同理；其中Distance為對應(yīng)的行號或者列號。兩重for循環(huán)遍歷所有組合的點(diǎn)，如果str1i = str2j，則Distanceij = Distancei - 1j - 1，handleij = 4;否則handleij = minval(Distancei - 1j + 1, Distanceij - 1 + 1, Distancei - 1j - 1 + 1, Distanceij); minval函數(shù)的作用是比較最大值，并返回最大值對應(yīng)的操作，1為刪除，2為插入，3為替換，當(dāng)循環(huán)結(jié)束時，在Distanc

9、em-1n-1（m,n分別為兩字符串的長度）中存儲著最少操作次數(shù)輸出步驟：最后先遞歸，后操作，修改str1字符串，表示操作的步驟。#include stdafx.h#include#include#include#include using namespace std;#define MAX 1000int DistanceMAXMAX;int handleMAXMAX;const string OPERATOR_NAME4 = 刪除串a(chǎn)中的一個字符:,在串a(chǎn)插入一個元素:,將串a(chǎn)中的,字母換為另一個字母:;/比較最大值，并返回最大值對應(yīng)的操作，1為刪除，2為插入，3為替換int minval

10、(int x, int y, int z,int &d)if (x y)if (x z)d = x;return 1;elsed = z;return 3;elseif (y z)d = y;return 2;elsed = z;return 3;void PrintHandle(int i,int j,string &str1,string str2)if (handleij = 1)/刪除cout OPERATOR_NAME0 str1i endl;str1.erase(str1.begin() + i);cout 當(dāng)前a字符串： str1 endl;PrintHandle(i - 1,

11、j, str1, str2);else if (handleij = 2)/插入cout OPERATOR_NAME1 str2j endl;str1.insert(str1.begin() + i+1, str2j);cout 當(dāng)前a字符串： str1 endl;PrintHandle(i, j - 1, str1, str2);else if (handleij = 3)/替換cout OPERATOR_NAME2 str1i OPERATOR_NAME3 str2j endl;str1.erase(str1.begin() + i);str1.insert(str1.begin() +

12、i, str2j);cout 當(dāng)前a字符串： str1 str2.length()if (str1i-1 != str2j)cout OPERATOR_NAME0 str1i - 1 endl;str1.erase(str1.begin() + i - 1);cout 當(dāng)前a字符串： str1 0)PrintHandle(i - 1, j, str1, str2);elseif (str1i != str2j-1)cout OPERATOR_NAME1 str2j - 1 endl;str1.insert(str1.begin() + i, str2j - 1);cout 當(dāng)前a字符串： st

13、r1 0)PrintHandle(i, j - 1, str1, str2);/編輯距離函數(shù)，str1 str2為操作的字符串 void OUTdistance(string str1, string str2, int lenthofstr1, int lenthofstr2)int i, j;for (i = 0; ilenthofstr1; i+)if (str1i = str20)Distancei0 = i;handlei0 = 5;elseDistancei0 = i + 1;handlei0 = 3;for (i = 0; ilenthofstr2; i+)if (str10 =

14、 str2i)Distance0i = i;handle0i = 5;elseDistance0i = i + 1;handle0i = 3;for (i = 1; ilenthofstr1; i+)for (j = 1; jlenthofstr2; j+)/如果對應(yīng)的字符相等，原問題交給子問題處理，即不用任何操作if (str1i = str2j)Distanceij = Distancei - 1j - 1;handleij = 4;else/否則的話，對左、右、左上角的值進(jìn)行求最小值handleij = minval(Distancei - 1j + 1, Distanceij - 1

15、+ 1, Distancei - 1j - 1 + 1, Distanceij);cout 輸出步驟： endl;PrintHandle(lenthofstr1-1, lenthofstr2-1, str1, str2);cout 最少的操作次數(shù)是： Distancelenthofstr1 - 1lenthofstr2 - 1 endl;int STRChang()string str1, str2;cout 輸入第一個字符串： str1;cout 輸入第二個字符串： str2;int lenthofstr1 = str1.length();int lenthofstr2 = str2.len

16、gth();OUTdistance(str1, str2,lenthofstr1,lenthofstr2);system(pause);return 0;int _tmain(int argc, _TCHAR* argv)STRChang();return 0;3. 計算所有的子矩陣中和的最大值使用動態(tài)規(guī)劃：使用一個二維數(shù)組，其中numij存儲矩陣i*j的元素和。num存儲的方法是：numij += numi - 1j;循環(huán)輸入后就得到了矩陣元素和的二維數(shù)組。使用三個變量i,j,k來遍歷，一個矩陣大小是M*N的，那么使i從0到M，再使j從每一個i到M，遍歷所有行可能。再考慮列方向，直接在每一種

17、i,j組合下，進(jìn)行0到N的遍歷，那么這樣就等于是把所有子矩陣的情形給遍歷完了。每次遍歷的過程是：從i，j點(diǎn)開始，temp = numjk - numi - 1k，表示行為i-1到j(luò)，列為1到k的矩陣的值，nummax = max(nummax , 0) + temp表示i-1到j(luò)，列為1到k的矩陣中從k向上最大的子矩陣元素和，Max = max(nummax , Max)表示最大的子矩陣和，當(dāng)遍歷結(jié)束，就可以求出最大舉證和。思考：本算法可以求出100*100的矩陣 #include stdafx.h#include#include#include#include#includeusing namespace std;#define MAX 1000int numMAXMAX;void subMatrix()int n;int r, c;int i, j, k;srand(unsigned (time(0);cout 請輸入行列數(shù)： r c;memset(num, 0, sizeof(num);cout 輸入矩陣： endl;for (i = 1; i = r; i+)for (j = 1; j numij;numij += numi - 1j;/numij表示i行j列矩陣的元素和int temp = 0;/記錄一行的元素和int Max