当前课程知识点:程序设计基础 > 第六章 递推与动态规划 > 6.4 最长公共子序列问题 > 6.4.1 问题描述与理解
最后我们来看最长公共序列的问题
一个字母组成的序列
随意的去掉若干位置上的字母
剩下的部分成为原序列的一个子序列
现在有A和B两个字母序列
如果序列C即是A的子序列又是B的子序列
则称C为A和B的公共子序列
请你编程读入字母序列A和B
然后输出一个A和B的最长的公共子序列
这问题的描述比较抽象
为了更好的理解题意呢
我们还是用实际的例子来看一看比较好
假设我们的序列A呢是这样的一个序列
它是a b c b d a c b
那么我去掉一些位置上的字母 或者说
我挑一些字母去一拼
比方说我现在依顺序呢挑出了b a b 三个字母
那么这三个字母也就依顺序组成一个序列
我们就称为这个序列是A序列的一个子序列
如果有另外一个序列b d a c b 那么我们发现说
它也可以适当的选取某些位置上的字母
还依原来的顺序呢拼成b a b
所以呢b a b 这个子序列
是A和B的一个公共的子序列
题目呢要求A和B呢最长的一个子序列
我们仔细的去看A和B 可以找到这么一个序列
我们可以把它假设叫成C1
那么它是由b d a b依次组成的
A和B的最长的公共子序列呢不止这一个
我们还可以找到第二个C2
b c a b这么一个子序列呢
也是A和B的一个最长的公共子序列
题目呢只要求我们输出
最长的公共子序列中的其中一个就行了
-1.1 基础知识
-1.2 买菜问题
-1.3 数学运算
-1.4 补充说明
-1.5 总结
--1.5 总结
-程设论道
--程设论道
-师生问答
-第一章 编程初步--语法自测
-2.1 关于超级计算器的几点思考
-2.2 电子秤模拟 — 背景介绍及需求分析
-2.3 电子秤模拟 — 代码实现
-2.4 变量定义与变量类型
-2.5 猜数游戏与数据表示
-2.6 关于变量的讨论
--公告
-2.7 变量体现的计算思维
-程设论道
--程设论道
-师生问答
--师生问答
-第二章 变量与代数思维--语法自测
-3.1 谁做的好事——语义表示
-3.2 谁做的好事——真假检查
-3.3 谁做的好事——循环枚举
-3.4 谁是嫌疑犯——多重循环枚举
-3.5 谁是嫌疑犯——破案线索表示
-3.6 谁是嫌疑犯——用二进制枚举
-程设论道
--程设论道一
--程设论道二
--程设论道三
-师生问答
-第三章 逻辑推理与枚举解题--语法自测
-4.1 插花游戏
-4.2 筛法
-4.3 线性查找
-4.4 折半查找
--4.4.1 提问
-4.5 排序问题
-4.6 总结
--4.6.1 总结
-程设论道
--程设论道二:筛法
-师生问答
-第四章 筛法与查找--语法自测
-5.1 阶乘
-5.2 排序
-5.3 矩阵填充
-5.4 分书与八皇后
-5.5 青蛙过河
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答一
--师生问答二
-第五章 分治思想与递归--语法自测
-6.1 兔子数列问题
-6.2 分鱼问题
-6.3 橱窗的插花问题
-6.4 最长公共子序列问题
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第六章 递推与动态规划--语法自测
-7.1 统计记录总数
-7.2 统计活跃用户数
-7.3 统计在线时长
--7.3.2 结构
-7.4 总结
--7.4.1 总结
-程设论道
--程设论道
-师生问答
--师生问答
-第七章 文本数据处理--语法自测
-8.1 将数据组织成链表
-8.2 提高链表访问效率 —— 哈希链表
-8.3 以二进制文件存储链表
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第八章 非文本数据处理--语法自测
-9.1 自动售卖程序
-9.2 配制水果信息
-9.3 指定界面语言
-程设论道
--程设论道
-师生问答
--师生问答
-第九章 可配置的程序设计--语法自测