最长公共子序列实验报告

试验四.最长公共子序列(LCS)算法一．实验原理对于给定的两个序列A和B，如果序列C既是A的子序列，又是B的子序列，则称C是A和B的公共子序列，A和B的公共子序列可能不止一个，其中最长的那个序列称为公共子序列。

公共子序列在很多实际应用中起关键作用。

序列A={abdledefiess},B={abwdifgdefiesa}，最长公共子序列为C={defies}二．实验目的本次实验就是要找出两个序列XY的最长公共子序列LCS三．实验步骤1.查找公共子序列2.输出公共子序列核心算法代码如下：int **lcs_length(char p[],char q[],int **c,int **k,int m,int n){int i,j;for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(p[i-1]==q[j-1])//如果两个字母相等的情况{c[i][j]=c[i-1][j-1]+1;k[i][j]=1;}else{if(c[i-1][j]>=c[i][j-1])//两字母不等情况1{c[i][j]=c[i-1][j];k[i][j]=2;}else//两字母不等情况2{c[i][j]=c[i][j-1];k[i][j]=3;}}}}return c,k;}输出代码void print_lcs(int **k,char p[],int i,int j){if(i==0||j==0)return ;if(k[i][j]==1){print_lcs(k,p,i-1,j-1);//通过递归的方法按照输入的从头到尾的顺序输出LCScout<<p[i-1];}else if(k[i][j]==2)print_lcs(k,p,i-1,j);elseprint_lcs(k,p,i,j-1);}四.实验结果根据实验算法运行结果如下:以上算法表明可以正确的找出两个序列的最长公共子序列,达到了本次实验的目的.。

第1篇一、实验目的1. 理解动态规划的基本思想和方法。

2. 掌握动态规划在解决实际问题中的应用。

3. 提高编程能力和算法设计能力。

二、实验内容本次实验主要涉及以下四个问题：1. 斐波那契数列2. 最长公共子序列3. 最长递增子序列4. 零钱找零问题三、实验原理动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划的基本思想是将一个复杂问题分解成若干个相互重叠的子问题，然后按照子问题的顺序逐个求解，最后将这些子问题的解合并成原问题的解。

四、实验步骤及代码实现1. 斐波那契数列斐波那契数列是指这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, ...，其中每个数都是前两个数的和。

```cppinclude <iostream>using namespace std;int Fibonacci(int n) {if (n <= 1) {return 1;}int fib[n+1];fib[0] = 1;fib[1] = 1;for (int i = 2; i <= n; i++) {fib[i] = fib[i-1] + fib[i-2];}return fib[n];}int main() {int n;cout << "请输入斐波那契数列的项数：" << endl;cin >> n;cout << "斐波那契数列的第 " << n << " 项为：" << Fibonacci(n) << endl;return 0;}```2. 最长公共子序列给定两个序列A和B，找出它们的公共子序列中长度最长的序列。

```cppinclude <iostream>using namespace std;int LCSLength(string X, string Y) {int m = X.length();int n = Y.length();int L[m+1][n+1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0 || j == 0)L[i][j] = 0;else if (X[i-1] == Y[j-1])L[i][j] = L[i-1][j-1] + 1;elseL[i][j] = max(L[i-1][j], L[i][j-1]);}}return L[m][n];}int main() {string X = "AGGTAB";string Y = "GXTXAYB";cout << "最长公共子序列长度为：" << LCSLength(X, Y) << endl; return 0;}```3. 最长递增子序列给定一个序列，找出它的最长递增子序列。

最长公共子序列问题一．实验目的：1.加深对最长公共子序列问题算法的理解，实现最长公共子序列问题的求解算法；2.通过本次试验掌握将算法转换为上机操作；3.加深对动态规划思想的理解，并利用其解决生活中的问题。

二．实验内容：1.编写算法：实现两个字符串的最长公共子序列的求解；2.将输入与输出数据保存在文件之中，包括运行时间和运行结果；3.对实验结果进行分析。

三．实验操作：1.最长公共子序列求解：将两个字符串放到两个字符型数组中，characterString1和characterString2，当characterString1[m]= characterString2[m]时，找出这两个字符串m之前的最长公共子序列，然后在其尾部加上characterString1[m]，即可得到最长公共子序列。

当characterString1[m] ≠characterString2[m]时，需要解决两个子问题：即找出characterString1(m-1)和characterString2的一个最长公共子序列及characterString1和characterString2(m-1)的一个最长公共子序列，这两个公共子序列中较长者即为characterString1和characterString2的一个最长公共子序列。

2.动态规划算法的思想求解：动态规划算法是自底向上的计算最优值。

计算最长公共子序列长度的动态规划算法LCS-Length以characterString1和characterString2作为输入，输出两个数组result和judge1，其中result存储最长公共子序列的长度，judge1记录指示result的值是由那个子问题解答得到的，最后将最终的最长公共子序列的长度记录到result中。

以LCS-Length计算得到的数组judge1可用于快速构造序列最长公共子序列。

首先从judge1的最后开始，对judge1进行配对。

第1篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。

为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。

二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。

1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。

（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。

- 对每种算法进行时间复杂度和空间复杂度的分析。

- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。

（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。

- 编写三种排序算法的代码。

- 分析代码的时间复杂度和空间复杂度。

- 编写测试程序，生成随机测试数据，测试三种算法的性能。

- 比较三种算法的运行时间和内存占用。

2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。

（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。

- 分析贪心算法的正确性，并证明其最优性。

（3）实验步骤：- 分析活动选择问题的贪心策略。

- 编写贪心算法的代码。

- 分析贪心算法的正确性，并证明其最优性。

- 编写测试程序，验证贪心算法的正确性。

3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。

（2）实验内容：- 实现一个动态规划算法问题，如背包问题。

- 分析动态规划算法的正确性，并证明其最优性。

（3）实验步骤：- 分析背包问题的动态规划策略。

- 编写动态规划算法的代码。

- 分析动态规划算法的正确性，并证明其最优性。

- 编写测试程序，验证动态规划算法的正确性。

三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)。

实验报告一、实验目的写出你认为比较重要的实验目的1．理解动态规划的基本思想,了解最优子结构性质和子问题的重叠性质。

2．熟练掌握典型的动态规划问题。

掌握动态规划思想分析问题的一般方法,对较简单的问题能正确分析,并设计出动态规划算法,并能够用程序实现。

二、实验内容简短明确地写出实验的内容（选作题目）动态规划寻找最长公共子序列三、实验环境操作系统、调试软件名称、版本号，上机地点，机器台号Win10、dev-cpp5.2.0、dreamweaver cs6四、问题分析（1）分析要解决的问题，给出你的思路，可以借助图表等辅助表达。

当一个问题具有最优子结构时，我们就可以考虑使用动态规划法去实现，因此首先刻画最长公共子序列的最优子结构：设X=x1x2…xm和Y=y1y2…yn是两个序列，Z=z1z2…zk是这两个序列的一个最长公共子序列。

1. 如果xm=yn，那么zk=xm=yn，且Zk-1是Xm-1，Yn-1的一个最长公共子序列；2. 如果xm≠yn，那么zk≠xm，意味着Z是Xm-1，Y的一个最长公共子序列；3. 如果xm≠yn，那么zk≠yn，意味着Z是X，Yn-1的一个最长公共子序列。

从上面我们可以看出如果xm=yn，那么我们应该求解Xm-1，Yn-1的一个LCS，并且将xm=yn加入到这个LCS的末尾，这样得到的一个新的LCS就是所求。

如果xm≠yn，分别求Xm-1，Y的一个LCS和X，Yn-1的一个LCS。

其中较长者就是X和Y的一个LCS。

c[m][n]=c[m-1][n-1]+1;c[m][n]=max(c[m-1][n],c[m][m-1]);（2）分析利用你的想法解决该问题可能会有怎样的时空复杂度。

建立c[m][n]的过程中时间复杂度是Ο（mn），空间复杂度是Ο（mn）。

（3）其它（你认为需要在此说明的）五、问题解决（1）根据对问题的分析，写出解决办法。

计算最长公共子序列长度的动态规划算法LCSLength以x[]和y[]作为输入，输出两个数组b[][]和c[][]，其中c[][]存储最长公共子序列的长度，b[][]记录指示c[][]的值是由那个子问题解答得到的，最后将最终的最长公共子序列的长度记录到c[][]中。

求连续的最长公共子串•首先我们来分析一个简单例子。

•LCS(‘212325233’,’312123223’)=‘21232’•我们看是如何求解出来的,如下图,红色下划线表示已匹配。

分析•从前面例子可以看出解题思路：•每次都是将子串的每一位与母串的每一位比较，然后根据比较的结果找LCS。

因此，我们需要借助一个二维数组存储两个串比较后的结果，用１表示匹配成功，０表示不成功。

如匹配结果如下图(1),最长公共子串见图(2)。

进一步分析•在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。

通过改进矩阵的生成方式和设置标记变量，可以省去这部分时间。

下面是新的矩阵生成方式：算法•设置一个矩阵，记录两个串的匹配情况。

•当字符匹配的时候，不是简单的给相应元素赋上1，而是赋上其左上角元素的值加１。

•我们用两个标记变量来标记矩阵中值最大的元素的位置，在矩阵生成的过程中来判断•当前生成的元素的值是不是最大的，据此来改变标记变量的值，那么到矩阵完成的时候，最长匹配子串的位置和长度就已经出来了。

•显然该算法的时间复杂度为两个串的长度乘积。

for(i=1;i<=row;i++) {for(j=1;j<=col;j++) {if(s[i-1]==rs[j-1]) {lcs[i][j]=lcs[i-1][j-1]+1;}else{if(lcs[i-1][j]>=lcs[i][j-1]) {lcs[i][j]=lcs[i-1][j];}else {lcs[i][j] = lcs[i][j-1];}}}}return lcs[row][col];}。

最长公共子序列的研究报告在计算机科学和数学领域中，最长公共子序列（Longest Common Subsequence，简称LCS）问题是一个经典且具有重要意义的研究课题。

它不仅在理论研究方面具有深厚的价值，还在实际应用中发挥着关键作用。

最长公共子序列问题的定义相对简单直观。

给定两个序列，我们要找出它们之间最长的公共部分，这个公共部分中的元素顺序保持不变。

例如，对于序列“ABCDGH”和“AEDFHR”，它们的最长公共子序列是“ADH”。

那么，为什么我们要研究最长公共子序列问题呢？这主要是因为它在很多实际场景中都有应用。

在生物信息学中，比较 DNA 序列或蛋白质序列的相似性时，最长公共子序列可以帮助我们了解物种之间的进化关系。

在文件比较和版本控制方面，通过找出两个文本文件的最长公共子序列，可以快速确定它们之间的差异和相似之处，从而提高工作效率。

在自然语言处理中，分析句子结构和语义的相似性时，最长公共子序列也能提供有价值的信息。

接下来，让我们探讨一下如何求解最长公共子序列问题。

最常见的方法是动态规划。

动态规划是一种通过将复杂问题分解为子问题，并保存子问题的解来避免重复计算的方法。

假设我们有两个序列 X 和 Y，长度分别为 m 和 n。

我们创建一个二维数组 dpm ＋ 1n ＋ 1来保存中间计算的结果。

dpij表示序列 X 的前 i 个元素和序列 Y 的前 j 个元素的最长公共子序列的长度。

初始化时，dp 的第一行和第一列都为 0，因为当一个序列为空时，最长公共子序列的长度为 0。

然后，我们通过以下递推公式来填充 dp 数组：如果 Xi 1 ＝＝ Yj 1，那么 dpij ＝ dpi 1j 1 ＋ 1。

这意味着如果当前两个元素相等，那么它们构成了公共子序列的一部分，长度在前一个状态的基础上加 1。

如果 Xi 1!＝ Yj 1，那么 dpij ＝ max(dpi 1j, dpij 1)。

这表示如果当前两个元素不相等，那么最长公共子序列的长度要么是只考虑 X 序列前 i 1 个元素和 Y 序列前 j 个元素的最长公共子序列的长度，要么是只考虑 X 序列前 i 个元素和 Y 序列前 j 1 个元素的最长公共子序列的长度，取两者中的最大值。

课程名称算法分析与设计实验实验项目实验一实验时间__2011__ 年_5___月__ 16 日实验指导老师曹霑懋实验评分院系：计算机学院实验课程：算法分析与设计实验实验项目：实验一（动态规划法算法）指导老师：曹霑懋开课时间：2010 ～ 2011年度第 2学期专业：计算机科学与技术师范类班级：09级 2 班学生：程毅学号： 20092101056华南师范大学教务处课程名称算法分析与设计实验实验项目实验一实验时间__2011__ 年_5___月__ 16 日实验指导老师曹霑懋实验评分实验名称：动态规划算法（综合性实验）实验目标：使用动态规划法和回溯法生成两个长字符串的最优化比对结果。

实验任务：把两个字符串放在一个二维矩阵中，把相同的字符尽最大可能放入同一列（使得整个的比对总计分最大）。

字符串S1，S2 分别放在二维矩阵的第一行和第2行，不可错行。

字符可以在行内移动，通过插入空格使得共同的片段置于共同的列。

实验步骤：1.明确实验目标和实验任务2.理解实验所涉及到的最长公共子序列的算法3.编写程序实现求两个字符串的最长公共子序列的长度。

4.设计实验数据数据并运行程序，记录运行的结果程序代码:#include<iostream>#include<string>#include<iomanip>using namespace std;int dp[1000][1000];string str1,str2,s1,s2;int max(int a,int b,int c){if(a>b && a>c)return a;if(b>a && b>c)return b;if(c>a && c>b)return c;}int lcs(int len1,int len2){memset(dp,0,sizeof(dp));int i,j,x;课程名称算法分析与设计实验实验项目实验一实验时间__2011__ 年_5___月__ 16 日实验指导老师曹霑懋实验评分dp[0][1]=0;dp[1][0]=0;dp[1][1]=0;dp[0][0]=0;for(i=2;i<len1+2;i++){dp[i][1]=-2*(i-1);}for(j=2;j<len2+2;j++){dp[1][j]=-2*(j-1);}for(j=2;j<len2+2;j++){for(i=2;i<len1+2;i++){if(str1[i-2]==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);}}return dp[i-1][j-1];}void print(int len1,int len2){int i,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;课程名称算法分析与设计实验实验项目实验一实验时间__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] || 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<<s1[i];}cout<<endl;for(j=len1-1;j>=0;j--){cout<<s2[j];}cout<<endl;}int main(){int len1,len2;while(cin>>str1>>str2){len1=str1.size();len2=str2.size();cout<<lcs(len1,len2)<<endl;课程名称算法分析与设计实验实验项目实验一实验时间__2011__ 年_5___月__ 16 日实验指导老师曹霑懋实验评分for(int i=1;i<=len1+1;i++){for(int j=1;j<=len2+1;j++){cout<<setw(5)<<dp[i][j]<<" ";}cout<<endl;}print(len1,len2);}return 0;}数据测试：实验小结：通过这次实验，对动态规划法求最长公共子序列有更深的理解。