最长公共子序列（动态规划）报告.doc

算法设计与分析实验报告，附已通过源码，供学习参考，共勉♪ 目录摘要如下： 1.问题描述 2.实验目的 3.实验原理 4.实验设计 （包括输入格式、算法、输出格式） 5.实验结果与分析 （除了截图外，实验结果还用图表进行了分析） 6.结论 7.程序源码 【最长公共子序列（动态规划）】是一种经典的算法问题，主要应用于序列比对、文本处理等领域。本实验报告详尽地介绍了如何运用动态规划解决这一问题。 动态规划是一种解决复杂问题的有效方法，它通过将大问题分解为小问题，逐步构建出全局最优解。在最长公共子序列问题中，动态规划的思想体现为自底向上的计算过程。 **1. 问题描述** 问题的核心是找到两个序列 X 和 Y 的最长公共子序列（LCS），即在删除若干元素后，X 和 Y 都能变成的子序列。例如，序列 {B,C,D,B} 是 {A,B,C,B,D,A,B} 的子序列，通过下标 {2,3,5,7} 显示这种关系。最长公共子序列不仅要存在于两个序列中，还要尽可能长。 **2. 实验目的** 实验目的是熟悉动态规划算法，并熟练掌握最长公共子序列的计算方法。 **3. 实验原理** - **问题解析**： - 最直观的解决方法是穷举所有可能的子序列，但效率低下，因为子序列数量是指数级的。 - 动态规划方法通过观察问题的最优子结构来优化。如果序列 Xi 和 Yj 有公共元素，LCS 可以通过将 Xi-1 和 Yj-1 的 LCS 加上这个共同元素得到；否则，LCS 是 Xi-1 和 Yj 或 Xi 和 Yj-1 中较长的那个。 - **递推关系**： - 定义二维数组 c[i][j]，表示序列 Xi 和 Yj 的 LCS 的长度。当 i 或 j 为 0 时，LCS 为空，长度为 0。当 Xi 和 Yj 相同，c[i][j] = c[i-1][j-1] + 1；否则，c[i][j] = max(c[i][j-1], c[i-1][j])。 - **构造最优解**： - 通过回溯二维数组 c 和辅助数组 b，可以找出具体的LCS。b[i][j] 用于指示LCS是通过哪个子问题得到的。 **4. 实验设计** - **输入数据格式**： - 输入两个序列的元素个数，程序通过随机数生成器创建特定规模的整型数组。 - **算法实现**： - 创建两个数组存储序列，通过 for 循环生成随机元素。 - 调用 lcsLength 函数，记录算法运行时间，并输出LCS。 - **输出结果**： - 打印两个序列，LCS 的长度，LCS 本身，以及算法运行时间。 **5. 实验结果与分析** 实验结果验证了算法的正确性，并通过测试用例评估了算法的时间复杂度，以证明其在大数据规模下的效率。 最长公共子序列问题的动态规划解决方案提供了一种高效的方法来找出两个序列之间的最长共享部分，这对于比较和分析序列数据至关重要。通过实验报告，我们可以深入理解动态规划的精髓，以及如何将理论知识应用到实际编程中。