《合工大程序设计艺术与方法实验四动态规划》由会员分享，可在线阅读，更多相关《合工大程序设计艺术与方法实验四动态规划（11页珍藏版）》请在金锄头文库上搜索。
1、. . .程序设计艺术与方法课程实验报告实验名称实验四 动态规划姓 名班 级学 号实验日期指导教师徐本柱成 绩一、实验目的和要求 理解动态规划的基本思想、动态规划算法的基本步骤。 掌握动态规划算法实际步骤。二、实验预习内容动态规划三、实验项目摘要 求两个字符串的最长公共子序列。X 的一个子序列是相应于X 下标序列1, 2, , m的一个子序列,求解两个序列的所有子序列中长度最大的,例如输入：pear, peach 输出：pea。 给定两个字符串a 和b,现将串a 通过变换变为串b,可用的操作为,删除串a 中的一个字符；在串a 的某个位置插入一个元素；将串a 中的某个字母换为另一个字母。对于任意
2、的串a 和串b,输出最少多少次能够将串变为串b。思考：输出变换的步骤。 输入一个矩阵,计算所有的子矩阵中和的最大值。例如,输入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的公共子序列的长度,其中当递归结束时,L
3、ongmn就存储着最大的长度。先将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 stdafx.h#include#incl
4、ude#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 LCSLengthint i, j;for i = 0; i Longi0 = 0;for j = 1; j Long0j = 0;/第一行第一列不使用,方便计算for i = 1; i for j = 1;
5、j if Longij = Longi - 1j - 1 + 1;seatij = 0;else if = Longij - 1Longij = Longi - 1j;seatij = 1;elseLongij = Longij - 1;seatij = -1;/以str1为标准输出bool Printif return true;if /先依次递归之后子序列,之后再输入该子序列符号,以保证输入的正确性Print;m = i;n = j;cout str1i - 1;return true;else if Print;elsePrint;void LCSstring str1, str2;in
6、t m = 0, n = 0, i = 0, j = 0;cout 输入第一个字符串： str1;cout 输入第二个字符串： str2;i = str1.length;j = str2.length;LCSLength;cout 最长子序列为： endl;Print;cout endl;cout 最长子序列长度为： Longmn endl;system;int _tmainLCS;return 0;2. 字符串的变换：使用动态规划的思想：定义两个数组,Distance表示距离,handle表示操作,其中handle存储的数1为删除,2为插入,3为替换,4为相同跳到下一个字符,5为结束状态。先
7、初始化,令handle开始的第一行第一列为5,如果str1i ！= str20,handle为3,列同理；其中Distance为对应的行号或者列号。两重for循环遍历所有组合的点,如果str1i = str2j,则Distanceij = Distancei - 1j - 1,handleij = 4;否则handleij = minval; minval函数的作用是比较最大值,并返回最大值对应的操作,1为删除,2为插入,3为替换,当循环结束时,在Distancem-1n-1m,n分别为两字符串的长度中存储着最少操作次数输出步骤：最后先递归,后操作,修改str1字符串,表示操作的步骤。#inc
8、lude stdafx.h#include#include#include#include using namespace std;#define MAX 1000int DistanceMAXMAX;int handleMAXMAX;const string OPERATOR_NAME4 = 删除串a中的一个字符:,在串a插入一个元素:,将串a中的,字母换为另一个字母:;/比较最大值,并返回最大值对应的操作,1为删除,2为插入,3为替换int minvalif x if x d = x;return 1;elsed = z;return 3;elseif y d = y;return 2;e
9、lsed = z;return 3;void PrintHandleif /删除cout OPERATOR_NAME0 str1i endl;str1.erasestr1.begin + i;cout 当前a字符串： str1 endl;PrintHandle;else if /插入cout OPERATOR_NAME1 str2j endl;str1.insertstr1.begin + i+1, str2j;cout 当前a字符串： str1 endl;PrintHandle;else if /替换cout OPERATOR_NAME2 str1i OPERATOR_NAME3 str2j endl;str1.erasestr1.begin + i;str1.insertstr1.begin + i, str2j;cout 当前a字符串： str1 endl;PrintHandle;else if PrintHandle;else if system;if str1.length str2.lengthif cout OPERATOR_NAME0 str1i - 1 endl;str1.erasestr1.begin + i - 1;cout 当前a字符串： str1 endl;if 0Print
