浙江工業(yè)大學算法實驗2 動態(tài)規(guī)劃算法實現

1、實驗2動態(tài)規(guī)劃算法實現一、實驗目標：熟悉動態(tài)規(guī)劃算法實現的基本方法和步驟；學會動態(tài)規(guī)劃算法的實現方法和分析方法：二、實驗內容：問題1：最長公共子序列的問題，測試數據X=ABCBDAB Y=BDCABAX=zhejiang university of technology Y= (zhejiang university city college1-1實驗代碼及截圖#include#include using namespace std;/求得兩個字符串的最大公共子序列長度int LCSLength(int m, int n,char* x, char* y,int *c, int *b)int

2、i, j, len;/i=0 | j=0for (i = 0; i m + 1; i+) ci0 = 0;for (j = 0; j 0for (i = 1; i = m; i+)for (j = 1; j = cij- 1)cij = ci- 1j;bij = 2;elsecij = cij- 1;bij = 3;len = cmn;return len;/構造最長公共子序列void LCS(int i, int j, char *x, int *b)if (i = 0 | j = 0) return;if (bij = 1)LCS(i - 1, j- 1, x, b);cout xi -

3、1;/ci對應 str1 的第 i-1 個元素 else if (bij = 2)LCS(i - 1, j, x, b);elseLCS(i, j- 1, x, b);int main()char str11000, str21000;int i, m, n, len;cout 請輸入第一個字符串：；gets_s(str1);cout 請輸入第二個字符串：； gets_s(str2);m = strlen(strl);n = strlen(str2);int *c = new int*m + 1; /彳亍for (i = 0; i m + 1; i+)ci = new intn + 1;/列i

4、nt *b = new int*m + 1;for (i = 0; i m + 1; i+)bi = new intn + 1;len = LCSLength(m, n, str1, str2, c, b);cout 最長公共子序列的長度為： len endl;cout (最長公共子序列為：)；LCS(m, n, str1, b);cout endl;system(pause);return 0;實驗截圖： Fc-PrActicecxieCakulateMethDd&De-bugCAkuhtcMethDdLexeEhejiog university of tocluioloffy ij輸人J(

5、5 二個子符暗：zhejiiijig university city college 歸女會共子洋列曲以為* a& 最氏公共子序列為e zhejiang iin s vers i tyfi-jiaay 訥按任意世姓姓. .1-2實驗總結：實驗最開始考慮到窮舉，但很明顯時間復雜度過于龐大，利用最長公共子序列的最優(yōu)子結構 性質，結合書上代碼進行實驗，但實驗中很明顯沒有考慮多種最長公共子序列的情況，這個 可能要留待后續(xù)繼續(xù)學習改進。1-3參考書籍：本書部分代碼。2.最大子段和問題，比較三重循環(huán)，分治法和動態(tài)規(guī)劃算法的效果，測試數據:(-2,11,-4,13,-5,-2)過去大約三百年間，太陽黑子數的

6、時間數據如該鏈接所示，請問，歷史上何時太陽黑子迎來了最大爆發(fā)？2.1-1 .實驗代碼及截圖#includeusing namespace std;int MaxSum1(int n, int *a, int& besti, int& bestj)int sum = 0;for (int i = 1; i = n; i+)for (int j = i; j = n; j+)int thissum = 0;for (int k = i; k sum)sum = thissum;besti = i;bestj = j;return sum;int MaxSum2(int* a, int left,

7、int right)int sum = 0;if (left = right)sum = aleft 0 ? aleft : 0;elseint center = (left + right) / 2;int leftsum = MaxSum2(a, left, center);int rightsum = MaxSum2(a, center + 1, right);int s1 = 0;int lefts = 0;for (int i = center; i = left; i-)lefts += ai;if (lefts s1)s1 = lefts;int s2 = 0;int right

8、s = 0;for (int i = center + 1; i s2)s2 = rights;sum = s1 + s2;if (sum leftsum)sum = leftsum;if (sum rightsum)sum = rightsum;return sum;int MaxSum3(int n, int *a)int sum = 0, b = 0;for (int i = 1; i 0) b += ai;else b = ai;if (b sum)sum = b;return sum;int main()int n,besti, bestj;int a = -2, 11,-4, 13

9、,-5,-2 ;cout 三重循環(huán):MaxSum1(6, a, besti, bestj) endl;cout 分治法: MaxSum2(a, 1, 6) endl;cout 動態(tài)規(guī)劃: MaxSum3(6, a) endl;system(pause);實驗截圖：2實驗總結：三重循環(huán)時間復雜度為n*n*n,分治法時間復雜度為nlogn,動態(tài)規(guī)劃時間復雜度為n 簡單窮舉是最容易想到的，但是論間接性或時間空間復雜度都是動態(tài)規(guī)劃更加優(yōu)越，通過實 驗感受動態(tài)規(guī)劃的魅力3參考書籍：本書部分代碼。1實驗代碼及截圖#include#include#include#include #include using

10、 namespace std;double MaxSum1(int n, double *a, int& besti, int& bestj) double sum = 0;for (int i = 1; i = n; i+)for (int j = i; j = n; j+)double thissum = 0;for (int k = i; k sum)sum = thissum;besti = i;bestj = j;return sum;double MaxSum2(double* a, int left, int right)double sum = 0;if (left = rig

11、ht)sum = aleft 0 ? aleft : 0;elseint center = (left + right) / 2;double leftsum = MaxSum2(a, left, center);double rightsum = MaxSum2(a, center + 1, right);double si = 0;double lefts = 0;for (int i = center; i = left; i-)lefts += ai;if (lefts si)si = lefts;double s2 = 0;double rights = 0;for (int i =

12、 center + 1; i s2)s2 = rights;sum = si + s2;if (sum leftsum)sum = leftsum;if (sum rightsum)sum = rightsum;return sum;double MaxSum3(int n, double *a)double sum = 0, b = 0;for (int i = 1; i 0) b += ai;else b = ai;if (b sum)sum = b;return sum;int main() ifstream myfile(f:太 陽黑子.txt);if (!myfile.is_open

13、() cerr 文件打不開 endl;return 0;vector vec;string temp;while (getline(myfile, temp)vec.push_back(temp);double a500;int i = 0;for (auto j = vec.begin(); j != vec.end(); j+)istringstream is(*j);string s;int tmp = 0;while (is s)if (tmp = 2) double r = atof(s.c_str();ai+ = r;tmp+;i-;/int sum;int besti, best

14、j;clock_t cstart, cends;cstart = clock();double sum1 = MaxSum1(i, a, besti, bestj);cends = clock();int t1 = cends - cstart;cstart = clock();double sum2 = MaxSum2(a, 1, i);cends = clock();int t2 = cends - cstart;cstart = clock();double sum3 = MaxSum3(i,a);cends = clock();int t3 = cends - cstart;cout 太陽黑子最大爆發(fā)年份：;cout vec.at(bestj) endl;/cout vec.at(sum) endl;cout 三重循環(huán)用時： t1 毫秒 endl;cout 分治法用時： t2 毫秒 endl;cout 動態(tài)規(guī)劃用時：t3 毫秒 endl; system(pause);實驗截圖2.2-2實驗總結：實驗中最大字段和算法