欢迎来到天天文库
浏览记录
ID:50128949
大小:35.50 KB
页数:5页
时间:2020-03-05
《最长公共子序列代码和实验报告.doc》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、院系:计算机学院实验课程:算法分析与设计实验实验项目:实验一(动态规划法算法)指导老师:曹霑懋开课时间:2010~2011年度第2学期专业:计算机科学与技术师范类班级:09级2班学生:程毅学号:20092101056华南师范大学教务处实验名称:动态规划算法(综合性实验)实验目标:使用动态规划法和回溯法生成两个长字符串的最优化比对结果。实验任务:把两个字符串放在一个二维矩阵中,把相同的字符尽最大可能放入同一列(使得整个的比对总计分最大)。字符串S1,S2分别放在二维矩阵的第一行和第2行,不可错行。字符可以在行内移动,通过插入空格使得
2、共同的片段置于共同的列。实验步骤:1.明确实验目标和实验任务2.理解实验所涉及到的最长公共子序列的算法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
3、)returnb;if(c>a&&c>b)returnc;}intlcs(intlen1,intlen2){memset(dp,0,sizeof(dp));inti,j,x;dp[0][1]=0;dp[1][0]=0;dp[1][1]=0;dp[0][0]=0;for(i=2;i4、]==str2[j-2])x=dp[i-1][j-1]+5;elsex=dp[i-1][j-1]-1;dp[i][j]=max(x,dp[i-1][j]-2,dp[i][j-1]-2);}}returndp[i-1][j-1];}voidprint(intlen1,intlen2){inti,j;i=len1+1;j=len2+1;while(i>1&&j>1){if(dp[i][j]+2==dp[i-1][j]){s2=s2+'_';s1=s1+str1[i-2];i--;continue;}if(dp[i][j]+2==dp[5、i][j-1]){s1=s1+'_';s2=s2+str2[j-2];j--;continue;}if(dp[i][j]+1==dp[i-1][j-1]6、7、dp[i][j]-5==dp[i-1][j-1]){s1=s1+str1[i-2];s2=s2+str2[j-2];j--;i--;continue;}}for(i=len1-1;i>=0;i--){cout<=0;j--){cout<8、len2;while(cin>>str1>>str2){len1=str1.size();len2=str2.size();cout<9、动态规划依赖于上一个或者上一行的解。就是在输出子序列的时候有问题。就是一开始,不知道那个横线放在哪里。后来修改过后终于行了。总得来说,实验还是很顺利的。遗憾的是,没有完全吃透思想。今年参加在华工举行的“亚联杯”程序设计大赛的时候也有一个求最长公共子序列的,但是没有做出来,因为没有优化好,有点遗憾,都超时了。哎……
4、]==str2[j-2])x=dp[i-1][j-1]+5;elsex=dp[i-1][j-1]-1;dp[i][j]=max(x,dp[i-1][j]-2,dp[i][j-1]-2);}}returndp[i-1][j-1];}voidprint(intlen1,intlen2){inti,j;i=len1+1;j=len2+1;while(i>1&&j>1){if(dp[i][j]+2==dp[i-1][j]){s2=s2+'_';s1=s1+str1[i-2];i--;continue;}if(dp[i][j]+2==dp[
5、i][j-1]){s1=s1+'_';s2=s2+str2[j-2];j--;continue;}if(dp[i][j]+1==dp[i-1][j-1]
6、
7、dp[i][j]-5==dp[i-1][j-1]){s1=s1+str1[i-2];s2=s2+str2[j-2];j--;i--;continue;}}for(i=len1-1;i>=0;i--){cout<=0;j--){cout<8、len2;while(cin>>str1>>str2){len1=str1.size();len2=str2.size();cout<9、动态规划依赖于上一个或者上一行的解。就是在输出子序列的时候有问题。就是一开始,不知道那个横线放在哪里。后来修改过后终于行了。总得来说,实验还是很顺利的。遗憾的是,没有完全吃透思想。今年参加在华工举行的“亚联杯”程序设计大赛的时候也有一个求最长公共子序列的,但是没有做出来,因为没有优化好,有点遗憾,都超时了。哎……
8、len2;while(cin>>str1>>str2){len1=str1.size();len2=str2.size();cout<9、动态规划依赖于上一个或者上一行的解。就是在输出子序列的时候有问题。就是一开始,不知道那个横线放在哪里。后来修改过后终于行了。总得来说,实验还是很顺利的。遗憾的是,没有完全吃透思想。今年参加在华工举行的“亚联杯”程序设计大赛的时候也有一个求最长公共子序列的,但是没有做出来,因为没有优化好,有点遗憾,都超时了。哎……
9、动态规划依赖于上一个或者上一行的解。就是在输出子序列的时候有问题。就是一开始,不知道那个横线放在哪里。后来修改过后终于行了。总得来说,实验还是很顺利的。遗憾的是,没有完全吃透思想。今年参加在华工举行的“亚联杯”程序设计大赛的时候也有一个求最长公共子序列的,但是没有做出来,因为没有优化好,有点遗憾,都超时了。哎……
此文档下载收益归作者所有