最长公共子序列代码和实验报告

《最长公共子序列代码和实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、华南师范大学实验报告学生姓名程毅学号20092101056专业计算机科学与技术（师范）年级、班级09级2班_课程名称算法分析与设计实验实验项目实验一实验时间__2011__年_5___月__16日实验指导老师曹霑懋实验评分院系：计算机学院实验课程：算法分析与设计实验实验项目：实验一（动态规划法算法）指导老师：曹霑懋开课时间：2010～2011年度第2学期专业：计算机科学与技术师范类班级：09级2班学生：程毅学号：20092101056华南师范大学教务处第5页/共5页华南师范大学实验报告学生姓名程毅学号20092101056专业计算机科学与技术（师范）年级

2、、班级09级2班_课程名称算法分析与设计实验实验项目实验一实验时间__2011__年_5___月__16日实验指导老师曹霑懋实验评分实验名称：动态规划算法（综合性实验）实验目标：使用动态规划法和回溯法生成两个长字符串的最优化比对结果。实验任务：把两个字符串放在一个二维矩阵中，把相同的字符尽最大可能放入同一列（使得整个的比对总计分最大）。字符串S1，S2分别放在二维矩阵的第一行和第2行，不可错行。字符可以在行内移动，通过插入空格使得共同的片段置于共同的列。实验步骤：1.明确实验目标和实验任务2.理解实验所涉及到的最长公共子序列的算法3.编写程序实现求两个字

3、符串的最长公共子序列的长度。4.设计实验数据数据并运行程序，记录运行的结果程序代码:#include#include#includeusingnamespacestd;intdp[1000][1000];stringstr1,str2,s1,s2;intmax(inta,intb,intc){if(a>b&&a>c)returna;if(b>a&&b>c)returnb;if(c>a&&c>b)returnc;}intlcs(intlen1,intlen2){memset(dp,0,sizeof(dp

4、));inti,j,x;第5页/共5页华南师范大学实验报告学生姓名程毅学号20092101056专业计算机科学与技术（师范）年级、班级09级2班_课程名称算法分析与设计实验实验项目实验一实验时间__2011__年_5___月__16日实验指导老师曹霑懋实验评分dp[0][1]=0;dp[1][0]=0;dp[1][1]=0;dp[0][0]=0;for(i=2;i

5、r(i=2;i1&&j>1){if(dp[i][j]+2==dp[i-1][j]){s2=s2+'_';s1=s1+str1[i-2];i--;continue;

6、第5页/共5页华南师范大学实验报告学生姓名程毅学号20092101056专业计算机科学与技术（师范）年级、班级09级2班_课程名称算法分析与设计实验实验项目实验一实验时间__2011__年_5___月__16日实验指导老师曹霑懋实验评分}if(dp[i][j]+2==dp[i][j-1]){s1=s1+'_';s2=s2+str2[j-2];j--;continue;}if(dp[i][j]+1==dp[i-1][j-1]

7、

8、dp[i][j]-5==dp[i-1][j-1]){s1=s1+str1[i-2];s2=s2+str2[j-2];j--;i--

9、;continue;}}for(i=len1-1;i>=0;i--){cout<=0;j--){cout<>str1>>str2){len1=str1.size();len2=str2.size();cout<

10、法分析与设计实验实验项目实验一实验时间__2011__年_5___月__16日实