合工大程序设计艺术与方法实验四动态规划

1、word 程序设计艺术与方法 课程实验报告实验名称实验四 动态规划姓 名班 级学 号实验日期指导教师徐本柱成 绩一、实验目的和要求(1) 理解动态规划的根本思想、动态规划算法的根本步骤。(2) 掌握动态规划算法实际步骤。二、实验预习内容动态规划三、实验工程摘要(1) 求两个字符串的最长公共子序列。X 的一个子序列是相应于X 下标序列1, 2, , m的一个子序列，求解两个序列的所有子序列中长度最大的，例如输入：pear, peach 输出：pea。(2) 给定两个字符串a 和b，现将串a 通过变换变为串b，可用的操作为，删除串a 中的一个字符；在串a 的某个位置插入一个元素；将串a 中的某个字

2、母换为另一个字母。对于任意的串a 和串b，输出最少多少次能够将串变为串b。思考：输出变换的步骤。(3) 输入一个矩阵，计算所有的子矩阵中和的最大值。例如，输入0 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2输出为：15四、实验结果与分析源程序及相关说明1. 求两个字符串的最长公共子序列算法思想：通过动态规划求解：seat二维数组用于表示选择的最长公共子序列以及输出时选择的方向，其中0表示可选的子序列点，1表示递归选择str10，i-1，str20，j)的公共子序列,-1选择str10，i，str20，j-1)的公共子序列，Long表示选择str10，i，str20，j)的

3、公共子序列的长度，其中当递归结束时，Longmn就存储着最大的长度。先将Long数组第一行第一列初始化为0，方便计算，接着如果stri = strj,那么seatij为可选点，seatij=0，同时Longij = Longi - 1j - 1 + 1，如果stri ！= strj，那么Longij=maxLongi - 1j Longij - 1，如果选择前者seatij=1，否那么seatij=-1；当循环遍历了两个字符串后，就得出结论，在根据seat中存储的元素值，从m，n开始m,n分别为两字符串的长度，先递归，后输出对应位置在字符串中的字符，递归结束，就可以输出字符串。#include

4、 #include#include#includeusing namespace std;#define MAXLEN 100int seatMAXLENMAXLEN;/其中0表示可选的子序列点，1表示选择str10，i-1，str20，j)的公共子序列,-1选择str10，i，str20，j-1)的公共子序列int LongMAXLENMAXLEN;/表示选择str10，i，str20，j)的公共子序列的长度void LCSLength(string str1, string str2, int m, int n)int i, j;for (i = 0; i = m; i+)Longi0 =

5、 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为标准输出bool Print(string str1, int i, int j,int &m,int &n)if (i = 0 | j = 0)return true;if (seatij = 0)/先依次递归之后子序列，之后再输入该子序列符号，以保

6、证输入的正确性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 = ();j = ();LCSLength(str1, str2,i,j);cou

7、t 最长子序列为： endl;Print(str1, i, j, m, n);cout endl;cout 最长子序列长度为： Longmn endl;system(pause);int _tmain(int argc, _TCHAR* argv)LCS();return 0;2. 字符串的变换：使用动态规划的思想：定义两个数组，Distance表示距离，handle表示操作，其中handle存储的数1为删除，2为插入，3为替换，4为相同跳到下一个字符，5为结束状态。先初始化，令handle开始的第一行第一列为5，如果str1i ！= str20，handle为3，列同理；其中Distance

8、为对应的行号或者列号。两重for循环遍历所有组合的点，如果str1i = str2j，那么Distanceij = Distancei - 1j - 1，handleij = 4;否那么handleij = minval(Distancei - 1j + 1, Distanceij - 1 + 1, Distancei - 1j - 1 + 1, Distanceij); minval函数的作用是比拟最大值，并返回最大值对应的操作，1为删除，2为插入，3为替换，当循环结束时，在Distancem-1n-1m,n分别为两字符串的长度中存储着最少操作次数输出步骤：最后先递归，后操作，修改str1字

9、符串，表示操作的步骤。#include #include#include#include#include using namespace std;#define MAX 1000int DistanceMAXMAX;int handleMAXMAX;const string OPERATOR_NAME4 = 删除串a中的一个字符:,在串a插入一个元素:,将串a中的,字母换为另一个字母:;/比拟最大值，并返回最大值对应的操作，1为删除，2为插入，3为替换int minval(int x, int y, int z,int &d)if (x y)if (x z)d = x;return 1;els

10、ed = 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;() + i);cout 当前a字符串： str1 endl;PrintHandle(i - 1, j, str1, str2);else if (handleij = 2)/插入cout OPERATOR_NAME1 str2j endl;() + i+1, st

11、r2j);cout 当前a字符串： str1 endl;PrintHandle(i, j - 1, str1, str2);else if (handleij = 3)/替换cout OPERATOR_NAME2 str1i OPERATOR_NAME3 str2j endl;() + i);() + i, str2j);cout 当前a字符串： str1 ()if (str1i-1 != str2j)cout OPERATOR_NAME0 str1i - 1 endl;() + i - 1);cout 当前a字符串： str1 0)PrintHandle(i - 1, j, str1, st

12、r2);elseif (str1i != str2j-1)cout OPERATOR_NAME1 str2j - 1 endl;() + i, str2j - 1);cout 当前a字符串： str1 0)PrintHandle(i, j - 1, str1, str2);/编辑距离函数，str1 str2为操作的字符串 void OUTdistance(string str1, string str2, int lenthofstr1, int lenthofstr2)int i, j;for (i = 0; ilenthofstr1; i+)if (str1i = str20)Distan

13、cei0 = i;handlei0 = 5;elseDistancei0 = i + 1;handlei0 = 3;for (i = 0; ilenthofstr2; i+)if (str10 = str2i)Distance0i = i;handle0i = 5;elseDistance0i = i + 1;handle0i = 3;for (i = 1; ilenthofstr1; i+)for (j = 1; jlenthofstr2; j+)/如果对应的字符相等，原问题交给子问题处理，即不用任何操作if (str1i = str2j)Distanceij = Distancei - 1

14、j - 1;handleij = 4;else/否那么的话，对左、右、左上角的值进行求最小值handleij = minval(Distancei - 1j + 1, Distanceij - 1 + 1, Distancei - 1j - 1 + 1, Distanceij);cout 输出步骤： endl;PrintHandle(lenthofstr1-1, lenthofstr2-1, str1, str2);cout 最少的操作次数是： Distancelenthofstr1 - 1lenthofstr2 - 1 endl;int STRChang()string str1, str2

15、;cout 输入第一个字符串： str1;cout 输入第二个字符串： str2;int lenthofstr1 = ();int lenthofstr2 = ();OUTdistance(str1, str2,lenthofstr1,lenthofstr2);system(pause);return 0;int _tmain(int argc, _TCHAR* argv)STRChang();return 0;3. 计算所有的子矩阵中和的最大值使用动态规划：使用一个二维数组，其中numij存储矩阵i*j的元素和。num存储的方法是：numij += numi - 1j;循环输入后就得到了矩阵

16、元素和的二维数组。使用三个变量i,j,k来遍历，一个矩阵大小是M*N的，那么使i从0到M，再使j从每一个i到M，遍历所有行可能。再考虑列方向，直接在每一种i,j组合下，进行0到N的遍历，那么这样就等于是把所有子矩阵的情形给遍历完了。每次遍历的过程是：从i，j点开始，temp = numjk - numi - 1k，表示行为i-1到j，列为1到k的矩阵的值，nummax = max(nummax , 0) + temp表示i-1到j，列为1到k的矩阵中从k向上最大的子矩阵元素和，Max = max(nummax , Max)表示最大的子矩阵和，当遍历结束，就可以求出最大举证和。思考：本算法可以求

17、出100*100的矩阵#include #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 请输入行列数： 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 = num11;int n