《最长公共子序列 代码和实验报告》由会员分享,可在线阅读,更多相关《最长公共子序列 代码和实验报告(5页珍藏版)》请在金锄头文库上搜索。
1、华华 南南 师师 范范 大大 学学 实实 验验 报报 告告学生姓名学生姓名 程毅程毅 学学 号号 20092101056 专专 业业 计算机科学与技术(师范)计算机科学与技术(师范) 年级、班级年级、班级 09 级级 2 班班 _ 课程名称课程名称 算法分析与设计实验算法分析与设计实验 实验项目实验项目 实验一实验一 实验时间实验时间 _2011_ 年年 _5_月月 _ 16 日日 实验指导老师 曹霑懋 实验评分 第 1 页/共 6 页院院 系:计系:计 算算 机机 学学 院院实验课程:算法分析与设计实验实验课程:算法分析与设计实验实验项目:实验一(动态规划法算法)实验项目:实验一(动态规划法
2、算法)指导老师:指导老师: 曹霑懋曹霑懋开课时间:开课时间:20102010 20112011 年度第年度第 2 2 学期学期专专 业:计算机科学与技术业:计算机科学与技术 师范类师范类班班 级:级:0909 级级 2 2 班班学学 生:生: 程毅程毅学学 号:号: 2009210105620092101056华南师范大学教务处华南师范大学教务处华华 南南 师师 范范 大大 学学 实实 验验 报报 告告学生姓名学生姓名 程毅程毅 学学 号号 20092101056 专专 业业 计算机科学与技术(师范)计算机科学与技术(师范) 年级、班级年级、班级 09 级级 2 班班 _ 课程名称课程名称 算
3、法分析与设计实验算法分析与设计实验 实验项目实验项目 实验一实验一 实验时间实验时间 _2011_ 年年 _5_月月 _ 16 日日 实验指导老师 曹霑懋 实验评分 第 2 页/共 6 页实验名称:实验名称:动态规划算法(综合性实验)实验目标:实验目标:使用动态规划法和回溯法生成两个长字符串的最优化比对结果。实验任务:实验任务:把两个字符串放在一个二维矩阵中,把相同的字符尽最大可能放入同一列(使得整个的比对总计分最大) 。字符串 S1,S2 分 别放在二维矩阵的第一行和第 2 行,不可错行。字符可以在行 内移动,通过插入空格使得共同的片段置于共同的列。实验步骤:实验步骤:1.明确实验目标和实验
4、任务2.理解实验所涉及到的最长公共子序列的算法3.编写程序实现求两个字符串的最长公共子序列的长度。4.设计实验数据数据并运行程序,记录运行的结果程序代码程序代码: #include #include #include using namespace std;int dp10001000; string str1,str2,s1,s2;int max(int a,int b,int c) if(ab if(ba if(ca int lcs(int len1,int len2) memset(dp,0,sizeof(dp);华华 南南 师师 范范 大大 学学 实实 验验 报报 告告学生姓名学生姓名
5、 程毅程毅 学学 号号 20092101056 专专 业业 计算机科学与技术(师范)计算机科学与技术(师范) 年级、班级年级、班级 09 级级 2 班班 _ 课程名称课程名称 算法分析与设计实验算法分析与设计实验 实验项目实验项目 实验一实验一 实验时间实验时间 _2011_ 年年 _5_月月 _ 16 日日 实验指导老师 曹霑懋 实验评分 第 3 页/共 6 页int i,j,x;dp01=0; dp10=0; dp11=0; dp00=0; for(i=2;i1 s1=s1+str1i-2; i-; continue;华华 南南 师师 范范 大大 学学 实实 验验 报报 告告学生姓名学生姓
6、名 程毅程毅 学学 号号 20092101056 专专 业业 计算机科学与技术(师范)计算机科学与技术(师范) 年级、班级年级、班级 09 级级 2 班班 _ 课程名称课程名称 算法分析与设计实验算法分析与设计实验 实验项目实验项目 实验一实验一 实验时间实验时间 _2011_ 年年 _5_月月 _ 16 日日 实验指导老师 曹霑懋 实验评分 第 4 页/共 6 页 if(dpij+2=dpij-1) s1=s1+_; s2=s2+str2j-2; j-; continue; if(dpij+1=dpi-1j-1 | dpij-5=dpi-1j-1) s1=s1+str1i-2; s2=s2+
7、str2j-2; j-; i-; continue; for(i=len1-1;i=0;i-) cout=0;j-) coutstr1str2) len1=str1.size(); len2=str2.size();华华 南南 师师 范范 大大 学学 实实 验验 报报 告告学生姓名学生姓名 程毅程毅 学学 号号 20092101056 专专 业业 计算机科学与技术(师范)计算机科学与技术(师范) 年级、班级年级、班级 09 级级 2 班班 _ 课程名称课程名称 算法分析与设计实验算法分析与设计实验 实验项目实验项目 实验一实验一 实验时间实验时间 _2011_ 年年 _5_月月 _ 16 日日
8、 实验指导老师 曹霑懋 实验评分 第 5 页/共 6 页coutlcs(len1,len2)endl; for(int i=1;i=len1+1;i+) for(int j=1;j=len2+1;j+) coutsetw(5)dpij“ “; coutendl; print(len1,len2); return 0; 数据测试:数据测试: 实验小结:实验小结:通过这次实验,对动态规划法求最长公共子序列有更深的理解。其实无 非就是抓住书上的递推公式进行写而已。动态规划依赖于上一个或者上一行的 解。就是在输出子序列的时候有问题。就是一开始,不知道那个横线放在哪里。 后来修改过后终于行了。总得来说,
9、实验还是很顺利的。遗憾的是,没有完全 吃透思想。今年参加在华工举行的“亚联杯”程序设计大赛的时候也有一个求 最长公共子序列的,但是没有做出来,因为没有优化好,有点遗憾,都超时了。华华 南南 师师 范范 大大 学学 实实 验验 报报 告告学生姓名学生姓名 程毅程毅 学学 号号 20092101056 专专 业业 计算机科学与技术(师范)计算机科学与技术(师范) 年级、班级年级、班级 09 级级 2 班班 _ 课程名称课程名称 算法分析与设计实验算法分析与设计实验 实验项目实验项目 实验一实验一 实验时间实验时间 _2011_ 年年 _5_月月 _ 16 日日 实验指导老师 曹霑懋 实验评分 第 6 页/共 6 页哎