中科大软院算法导论-第五次实验报告-最长公共子序列实验报告

最长公共子序列问题一．实验目的：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进行配对。

2.3最长公共子序列问题和前面讲的有所区别，这个问题的不涉及走向。

很经典的动态规划问题。

例题16最长公共子序列(lcs.pas/c/cpp)【问题描述】一个给定序列的子序列是在该序列中删去若干元素后得到的序列。

确切地说，若给定序列X= < x1, x2,…, xm>，则另一序列Z= < z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列< i1, i2,…, ik>，使得对于所有j=1,2,…,k有Xij=Zj例如，序列Z=是序列X=的子序列，相应的递增下标序列为<2,3,5,7>。

给定两个序列X 和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

例如，若X= < A, B, C, B, D, A, B>和Y= < B, D, C, A, B, A>，则序列是X和Y的一个公共子序列，序列也是X和Y的一个公共子序列。

而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。

给定两个序列X= < x1, x2, …, xm>和Y= < y1, y2, … , yn>，要求找出X和Y的一个最长公共子序列。

【输入文件】输入文件共有两行，每行为一个由大写字母构成的长度不超过200的字符串，表示序列X和Y。

【输出文件】输出文件第一行为一个非负整数，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出文件仅有一行输出一个整数0，否则在输出文件的第二行输出所求得的最长公共子序列(也用一个大写字母组成的字符串表示。

【输入样例】ABCBDABBDCBA【输出样例】4BCBA【问题分析】这个问题也是相当经典的。

这个题目的阶段很不明显，所以初看这个题目没什么头绪，不像前面讲的有很明显的上一步，上一层之类的东西，只是两个字符串而且互相没什么关联。

但仔细分析发现还是有入手点的：既然说是动态规划，那我们首先要考虑的就是怎么划分子问题，一般对于前面讲到的街道问题和数塔问题涉及走向的，考虑子问题时当然是想上一步是什么？但这个问题没有涉及走向，也没有所谓的上一步，该怎么办呢？既然是求公共子序列，也就有第一个序列的第i个字符和第二个序列的第j个字符相等的情况。

第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[][]中。

最长公共子序列的研究报告在计算机科学和数学领域中，最长公共子序列（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 个元素的最长公共子序列的长度，取两者中的最大值。

目录1 前言02 需求分析12.1 任务和要求12.2 运行环境12.3 开发工具13 分析和设计13.1 系统分析及设计思路13.2 主要数据结构及算法23.3 函数流程图24 具体代码实现35 课程设计总结135.1 程序运行结果或预期运行结果135.2 设计结论13参考文献14致谢141 前言若给定序列X={x1,x2,…,x m}，则另一序列Z={z1,z2,…,z k}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。

例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。

给定2个序列X和Y，当另一序列Z既是X的子序列又是Y 的子序列时，称Z是序列X和Y的公共子序列。

请使用C语言编程，设计一个有效的算法解决下述问题：给定2个序列X={x1,x2,…,x m}和Y={y1,y2,…,y n}，找出X和Y 的最长公共子序列。

2 需求分析2.1任务和要求使用C语言编程，设计一个有效的算法解决下述问题：给定2个序列X={x1,x2,…,x m}和Y={y1,y2,…,y n}，找出X和Y的最长公共子序列。

2.2运行环境（1）WINDOWS2000/XP系统（2）Visual C++ 6.0编译环境或TC编译环境2.3开发工具C语言3 分析和设计3.1 系统分析及设计思路设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,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的最长公共子序列。

由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。

第1篇一、实验背景随着计算机科学的不断发展，算法在各个领域都扮演着至关重要的角色。

为了更好地理解和掌握算法设计与应用，我们进行了本次算法实验。

本次实验旨在通过实际操作，加深对常见算法的理解，提高算法设计与分析能力。

二、实验目的1. 掌握常见算法的基本原理和实现方法。

2. 熟悉算法的时间复杂度和空间复杂度分析。

3. 培养团队协作精神和实验操作能力。

三、实验内容本次实验主要涉及以下算法：1. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。

2. 查找算法：顺序查找、二分查找、斐波那契查找。

3. 图算法：深度优先搜索（DFS）、广度优先搜索（BFS）、最短路径算法（Dijkstra算法、Floyd算法）。

四、实验过程1. 熟悉实验环境，安装必要的开发工具和库。

2. 分析每个算法的基本原理，编写代码实现。

3. 对每个算法进行时间复杂度和空间复杂度分析。

4. 对比不同算法的优缺点，总结适用场景。

5. 编写实验报告，总结实验心得。

五、实验结果与分析1. 排序算法（1）冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)，适用于小规模数据排序。

（2）选择排序：时间复杂度O(n^2)，空间复杂度O(1)，适用于小规模数据排序。

（3）插入排序：时间复杂度O(n^2)，空间复杂度O(1)，适用于部分有序数据排序。

（4）快速排序：时间复杂度O(nlogn)，空间复杂度O(logn)，适用于大规模数据排序。

（5）归并排序：时间复杂度O(nlogn)，空间复杂度O(n)，适用于大规模数据排序。

（6）堆排序：时间复杂度O(nlogn)，空间复杂度O(1)，适用于大规模数据排序。

2. 查找算法（1）顺序查找：时间复杂度O(n)，空间复杂度O(1)，适用于数据量较小的查找。

（2）二分查找：时间复杂度O(logn)，空间复杂度O(1)，适用于有序数据查找。

（3）斐波那契查找：时间复杂度O(logn)，空间复杂度O(1)，适用于有序数据查找。

最长公共子序列实验报告公司内部档案编码：[OPPTR-OPPT28-OPPTL98-OPPNN08]最长公共子序列问题一．实验目的：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可用于快速构造序列最长公共子序列。