当前课程知识点：程序设计基础 >  第六章 递推与动态规划 >  6.4 最长公共子序列问题 >  6.4.2 问题分析

返回《程序设计基础》慕课在线视频课程列表

6.4.2 问题分析在线视频

6.4.2 问题分析

下一节:6.4.3.1 动态规划解题(1)

返回《程序设计基础》慕课在线视频列表

6.4.2 问题分析课程教案、知识点、字幕

那么这个问题到底该怎么解决呢

那我们可以想一想如果人来去找的话

用眼睛来找的话 我们会怎么找

当然我们很自然就想到说

我肯定先把A和B的第一个字母拿出来比较一下

看他们是不是相等 用我们的代码的语言

计算机的语言来表示呢

表示成说A0和B0是不是相等的

如果他们两个相等 那我们一定很高兴

要找公共的子序列嘛 已经匹配上一个字母了

我们只需要找他们后面的部分

就是对于A来讲下标1开始的那个部分 那个序列

和B下标1开始的那个序列我们继续去比较就可以了

那如果A0和B0不等呢

那至少这个位置他们匹配不上

他们不是一个公共的子序列的部分

那我们就只能说可以想到别的方案

可以想到说 我就试图说挪挪位置

我把A去和B后面的串去比比看

他们的最长公共子序列是什么

那么这两个字母的序列是对称的

所以呢我们也要找一找说

B这个序列去和A从下标1的这个字母开始的

这么一个序列去比 我们也可以找找

这样情况下的最长公共子序列

那最后大不了把这两种情况的所谓的最长公共子序列

再比一次求一个最长的

那这就是我们一个很朴素的

人眼可以根据这个观察去操作的这么一个方法

我们可以用我们的这种数学的语言写更一般化一些

也就是说我其实呢是

去比较在A和B两个序列中的一个对应位置

比如说我比较Ai和Bj对应位置上的这么两个字母

如果他们相等呢我就很高兴

我就说我找到了一个公共的子序列的字母了

然后我只要比较它们剩余的部分了

也就是说我们可以说A从i+1开始的这么一个序列

和B从j+1这两个序列我们去比较就行了

那么如果Ai和Bj不等的话呢

那我们就给错开一个

或者说我们也可以解释成说

那么我们把不等这个位置的字母扔掉呗

如果我把Bj的这个字母扔掉

那我就去比较Ai开始的序列和Bj+1开始的序列

如果我把Ai这个字母扔掉

那我就去比较Ai+1开始的序列和Bj开始的序列

所以我们找到这两个序列求他们的

最长公共子序列就可以了

那我们再从头的看看我们到底应该怎么处理

因为大概有了这想法了

那原始问题呢显然是说我们从A0开始

和B0开始这两个序列进行比较

如果呢A0和B0相等那我可以认为说

两个序列都扔掉这个位置了进行比较

也就是我只要继续比较A1开始的序列和B1开始的序列

那么如果A0和B0不等 那我们扔掉一个

我们接着比较A0开始的序列和B1开始的序列

并且呢我们还要去看看A1开始的序列和B0开始的序列

然后我们再去找所谓的最长的公共子序列

反正在0这个位置上面它们是不可能都有相同字母的

好 对于A0和B0的这两个分支我们继续考察

如果A1和B1这两个字母是相同的

我们又找到了公共子序列的部分

那我们只需要去比较A2开始的序列和B2开始的序列了

如果他们不等呢

两种情况我们需要分别去比较

A1开始序列B2开始序列

和A2开始序列B1开始序列

同样例如说我们就对中间这种情况来看

如果A1和B2他们相等

那么我们就要比较A2开始和B3开始的序列

如果他们不等呢 又是两种情况

那从另一个分支来说呢

我们考虑这个对应位置的字母相等

有一种情况不等 有两种情况

我们现在只画了一部分

如果这个串比较长的话

我们可以想象到说我这个树状结构得画的非常非常复杂

细心的同学已经发现了

虽然我只画了很小的一部分

但是呢这里头明显是有一些重复的

比如说 我们在不同的分支

都需要比较A从1开始的序列和B从1开始的序列

我们在不同的分支都需要比较

A从2开始的序列和B从2开始的序列

我们在不同的分支还要都比较说

A从2开始序列和B从1开始的序列

那么这么多重复的计算

就是因为我们去设计我们这个计算

实际上我们已经学过了这是一个

典型的递归的一个算法的思想

这里头呢是存在着大量的重复计算的

而我们之前也已经学过了说

为了避免这样重复计算呢

我们可以去保存已经算出来的结果

也就是我们保存了A从i开始的串B从j开始的

这两个串的比较结果呢

以后如果还需要计算同样的情形

那我们就可以直接这样取值了

从而避免重复计算

那么这个是我们从人眼观察得到的

一个递推的一个递归的方法

那么今天呢

我们实际上已经介绍了动态规划的这种方法

所以呢我们将会尝试 用动态规划的方法来

重新解决这样一个求最长公共子序列的问题

程序设计基础课程列表：

第一章 编程初步

-1.1 基础知识

--1.1.1 什么是程序？什么是语言？

--1.1.2 什么是程序设计？

--1.1.3 计算机发展史

-1.2 买菜问题

--1.2.1 问题描述

--1.2.2 程序的基本结构

-1.3 数学运算

--1.3.1 数学运算符

--1.3.2 数学函数

-1.4 补充说明

--1.4.1 编程环境的下载与安装

--1.4.2 程序基本结构中的含义

--1.4.3 格式与风格

-1.5 总结

--1.5 总结

-程设论道

--程设论道

-师生问答

--师生问答一：怎样学好程序设计

--师生问答二：语言选择

--师生问答三：关于函数

-第一章 编程初步--语法自测

第二章 变量与代数思维

-2.1 关于超级计算器的几点思考

--2.1.1 关于超级计算器的几点思考

-2.2 电子秤模拟 — 背景介绍及需求分析

--2.2.1 电子秤模拟 — 背景介绍及需求分析

-2.3 电子秤模拟 — 代码实现

--2.3.1 电子秤模拟 — 代码实现

-2.4 变量定义与变量类型

--2.4.1 变量定义与变量类型

-2.5 猜数游戏与数据表示

--2.5.1 猜数游戏与数据表示

-2.6 关于变量的讨论

--2.6.1 变量的初始值

--2.6.2 变量类型

--2.6.3 变量内存单元地址

--2.6.4 存“变量地址”的变量——指针

--2.6.5 指针的 读/写 操作

--2.6.6 指针的 加/减 操作

--公告

-2.7 变量体现的计算思维

--2.7.1 变量体现的计算思维

-程设论道

--程设论道

-师生问答

--师生问答

-第二章 变量与代数思维--语法自测

第三章 逻辑推理与枚举解题

-3.1 谁做的好事——语义表示

--3.1.1 谁做的好事——语义表示

-3.2 谁做的好事——真假检查

--3.2.1 谁做的好事——真假检查

-3.3 谁做的好事——循环枚举

--3.3.1 谁做的好事——循环枚举

-3.4 谁是嫌疑犯——多重循环枚举

--3.4.1 谁是嫌疑犯——多重循环枚举

-3.5 谁是嫌疑犯——破案线索表示

--3.5.1 谁是嫌疑犯——破案线索表示

-3.6 谁是嫌疑犯——用二进制枚举

--3.6.1 谁是嫌疑犯——用二进制枚举

-程设论道

--程设论道一

--程设论道二

--程设论道三

-师生问答

--师生问答一：字符与ASCII码表

--师生问答二：其他循环语句、运算符优先级与变量作用域

-第三章 逻辑推理与枚举解题--语法自测

第四章 筛法与查找

-4.1 插花游戏

--4.1.1 问题提出（求素数）

--4.1.2 函数初探

--4.1.3 运行演示

-4.2 筛法

--4.2.1 筛法思路

--4.2.2 数组的定义

--4.2.3 代码翻译

--4.2.4 运行演示

--4.2.5 小朋友数人数

--4.2.6 运行演示

--4.2.7 韩信点兵

-4.3 线性查找

--4.3.1 扑克查找问题

--4.3.2 扑克查找问题代码翻译

--4.3.3 最小值问题

--4.3.4 最小值问题代码翻译

-4.4 折半查找

--4.4.1 提问

--4.4.2 折半查找思路

--4.4.3 折半查找代码翻译

--4.4.4 折半查找运行演示

-4.5 排序问题

--4.5.1 插入排序

--4.5.2 选择排序

--4.5.3 函数写法

--4.5.4 运行演示

-4.6 总结

--4.6.1 总结

-程设论道

--程设论道一：数组与编码思维

--程设论道二：筛法

-师生问答

--师生问答一：函数与面向过程编程

--师生问答二：数组的下标越界

-第四章 筛法与查找--语法自测

第五章 分治思想与递归

-5.1 阶乘

--5.1.1 阶乘问题

--5.1.2 递归解法

--5.1.3 递归小结

-5.2 排序

--5.2.1 归并排序——总体思路

--5.2.2 归并排序——思路分解

--5.2.3 归并排序——代码解说

--5.2.4 快速排序——总体思路

--5.2.5 快速排序——代码解说

--5.2.6 排序总结

-5.3 矩阵填充

--5.3.1 矩阵填充问题

--5.3.2 代码解说

-5.4 分书与八皇后

--5.4.1 问题描述

--5.4.2 问题分析——共性

--5.4.3 问题分析——区别

--5.4.4 解题准备——二维数组

--5.4.5 解题准备——递归设计

--5.4.6 代码解说——分书问题

--5.4.7 代码解说——八皇后问题

-5.5 青蛙过河

--5.5.1 问题描述

--5.5.2 问题分析——简单情况

--5.5.3 问题分析——复杂情况

--5.5.4 问题分析——一般情况

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答一

--师生问答二

-第五章 分治思想与递归--语法自测

第六章 递推与动态规划

-6.1 兔子数列问题

--6.1.1 问题描述

--6.1.2 按大小兔子分别递推

--6.1.3 按总数递推

--6.1.4 不用数组递推

-6.2 分鱼问题

--6.2.1 问题描述

--6.2.2 从A到E递推

--6.2.3 从E到A递推

-6.3 橱窗的插花问题

--6.3.1 问题描述

--6.3.2 题意理解与分析

--6.3.3 用枚举思想解题

--6.3.4 采用递推的优化算法

--6.3.5.1 采用动态规划算法—优化分析

--6.3.5.2 采用动态规划算法—递推代码

--6.3.5.3 采用动态规划算法—计算过程

--6.3.5.4 采用动态规划算法—输出方案

--6.3.6 动态规划总结

-6.4 最长公共子序列问题

--6.4.1 问题描述与理解

--6.4.2 问题分析

--6.4.3.1 动态规划解题(1)

--6.4.3.2 动态规划解题(2)

--6.4.3.3 动态规划代码

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答

-第六章 递推与动态规划--语法自测

第七章 文本数据处理

-7.1 统计记录总数

--7.1.1 问题分析

--7.1.2 读文件操作

-7.2 统计活跃用户数

--7.2.1 问题分析

--7.2.2 字符串

--7.2.3 程序翻译与演示

-7.3 统计在线时长

--7.3.1 问题分析

--7.3.2 结构

--7.3.3 程序翻译与演示

--7.3.4 写文件操作

-7.4 总结

--7.4.1 总结

-程设论道

--程设论道

-师生问答

--师生问答

-第七章 文本数据处理--语法自测

第八章 非文本数据处理

-8.1 将数据组织成链表

--8.1.1 链表的基本概念

--8.1.2 代码讲解

--8.1.3 链表遍历与释放

-8.2 提高链表访问效率 —— 哈希链表

--8.2.1 简单的哈希算法

--8.2.2 算法实现

-8.3 以二进制文件存储链表

--8.3.1 二进制文件的操作方法

--8.3.2 代码讲解

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答

-第八章 非文本数据处理--语法自测

第九章 可配置的程序设计

-9.1 自动售卖程序

--9.1.1 提出问题与初步设计

--9.1.2 细化实现订单处理

--9.1.3 使程序更健壮

-9.2 配制水果信息

--9.2.1 提出问题与设计文件格式

--9.2.2 实现订单处理功能

-9.3 指定界面语言

--9.3.1 提出问题与命令行参数

--9.3.2 实现程序功能

-程设论道

--程设论道

-师生问答

--师生问答

-第九章 可配置的程序设计--语法自测

6.4.2 问题分析笔记与讨论

也许你还感兴趣的课程:


  1. 游戏分析与评测(2021秋)

  2. 项目采购与合同管理(2021秋)

  3. 生物化学(2021秋)

  4. 计量经济学(2021秋)

  5. 数据链技术与系统(2021秋)

  6. 航空发动机控制(2021秋)

  7. 安全管理学(2021秋)

  8. 云南特色民间工艺(2021秋)

  9. 通过实验学电路(2021秋)

  10. 编译技术(2021秋)

  11. 程序设计基础(2021秋)

  12. 自我认知与情绪管理(2021秋)

  13. 大唐兴衰(2021秋)

  14. 生活、艺术与时尚：中国服饰七千年(2021秋)

  15. 中国房地产发展之路(2021秋)

  16. 计算机文化基础(2021秋)

  17. 宝玉石鉴赏(2021秋)

  18. 现代礼仪(2021秋)

  19. 中国古代礼义文明——礼学经典(2021秋)

  20. 住宅精细化设计(2021秋)
© 柠檬大学-慕课导航 课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。