浙江工业大学算法实验2 动态规划算法实现

1、实验2动态规划算法实现一、实验目标：熟悉动态规划算法实现的基本方法和步骤；学会动态规划算法的实现方法和分析方法：二、实验内容：问题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实验总结：实验最开始考虑到穷举，但很明显时间复杂度过于庞大，利用最长公共子序列的最优子结构 性质，结合书上代码进行实验，但实验中很明显没有考虑多种最长公共子序列的情况，这个 可能要留待后续继续学习改进。1-3参考书籍：本书部分代码。2.最大子段和问题，比较三重循环，分治法和动态规划算法的效果，测试数据:(-2,11,-4,13,-5,-2)过去大约三百年间，太阳黑子数的

6、时间数据如该链接所示，请问，历史上何时太阳黑子迎来了最大爆发？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 三重循环:MaxSum1(6, a, besti, bestj) endl;cout 分治法: MaxSum2(a, 1, 6) endl;cout 动态规划: MaxSum3(6, a) endl;system(pause);实验截图：2实验总结：三重循环时间复杂度为n*n*n,分治法时间复杂度为nlogn,动态规划时间复杂度为n 简单穷举是最容易想到的，但是论间接性或时间空间复杂度都是动态规划更加优越，通过实 验感受动态规划的魅力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 太阳黑子最大爆发年份：;cout vec.at(bestj) endl;/cout vec.at(sum) endl;cout 三重循环用时： t1 毫秒 endl;cout 分治法用时： t2 毫秒 endl;cout 动态规划用时：t3 毫秒 endl; system(pause);实验截图2.2-2实验总结：实验中最大字段和算法