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

《合工大程序设计艺术与方法 实验四 动态规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档《程序设计艺术与方法》课程实验报告实验名称实验四动态规划姓名班级学号实验日期2018.6.12指导教师徐本柱成绩一、实验目的和要求(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-7092-62-41-41文案大全实用文档-180-2输出为：15四、实验结果与分析（源程序及相关说明）1.求两个字符串的最长公共子序列算法思想：通过动态规划求解：seat二维数组用于表示选择的最长公共子序列以及输出时选择的方向，其中0表示可选的子序列点，1表示递归选择str1（0，i-1），str2（0，j)的公共子序列,-1选择str1（0，i），str2（0，j-1)的公共子序列，Long表示选择str1（0，i），str2（

3、0，j)的公共子序列的长度，其中当递归结束时，Long[m][n]就存储着最大的长度。先将Long数组第一行第一列初始化为0，方便计算，接着如果str[i]==str[j],则seat[i][j]为可选点，seat[i][j]=0，同时Long[i][j]=Long[i-1][j-1]+1，如果str[i]！=str[j]，则Long[i][j]=max（Long[i-1][j]Long[i][j-1]），如果选择前者seat[i][j]=1，否则seat[i][j]=-1；当循环遍历了两个字符串后，就得出结论，在根据seat中存储的元素值，从m，n开始（m,n分别为两字符串的长度）

4、，先递归，后输出对应位置在字符串中的字符，递归结束，就可以输出字符串。#include"stdafx.h"#include#include#includeusingnamespacestd;#defineMAXLEN100intseat[MAXLEN][MAXLEN];//其中0表示可选的子序列点，1表示选择str1（0，i-1），str2（0，j)的公共子序列,-1选择str1（0，i），str2（0，j-1)的公共子序列intLong[MAXLEN][MAXLEN];//表示选择str1（0，i），str2（0，j)的公共子序

5、列的长度文案大全实用文档voidLCSLength(stringstr1,stringstr2,intm,intn){inti,j;for(i=0;i<=m;i++)Long[i][0]=0;for(j=1;j<=n;j++)Long[0][j]=0;//第一行第一列不使用，方便计算for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(str1[i-1]==str2[j-1]){Long[i][j]=Long[i-1][j-1]+1;seat[i][j]=0;}elseif(Long[i-1][j]>=Long[i][j-1]){Long[i][j]=Long

6、[i-1][j];seat[i][j]=1;}else{Long[i][j]=Long[i][j-1];seat[i][j]=-1;文案大全实用文档}}}}//以str1为标准输出boolPrint(stringstr1,inti,intj,int&m,int&n){if(i==0

7、

8、j==0)returntrue;if(seat[i][j]==0){//先依次递归之后子序列，之后再输入该子序列符号，以保证输入的正确性Print(str1,i-1,j-1,m,n);m=i;n=j;cout<

9、nt(str1,i-1,j,m,n);elsePrint(str1,i,j-1,m,n);}voidLCS(){文案大全实用文档stringstr1,str2;intm=0,n=0,i=0,j=0;cout<<"输入第一个字符串："<>str1;cout<<"输入第二个字符串："<>str2;i=str1.length();j=str2.length();LCSLength(str1,str2,i,j);cout<<