当前课程知识点:程序设计基础 >  第五章 分治思想与递归 >  5.4 分书与八皇后 >  5.4.3 问题分析——区别

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

5.4.3 问题分析——区别在线视频

5.4.3 问题分析——区别

下一节:5.4.4 解题准备——二维数组

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

5.4.3 问题分析——区别课程教案、知识点、字幕

在讨论它们的算法

这个思路的描述之前

我们还有看一看这两个问题之间

有什么样的一种区别

除了刚才说这种斜线之外

我们如果仔细再思考的话

发现这两个问题在有

限制条件的这个上面是有一些区别的

对于分书这个问题

那么它设置元素的这个位置

它其实是有限制的

因为每本书能分给那些人

就是那些人喜欢那本书

这个是在题目里头给定了的

那所有的这样的一个分书的方案

只能是从

这些已经规定好的

这种偏好关系上去选择

换而言之

如果对于一个矩阵而言

就相当于

我是在矩阵里头画了一些区域

在这些区域里头

你才可以做一个分配的

这种元素的设置

那么其他没有这种喜好关系的

那些矩阵的元素的

这个位置是不可以填充元素呢

也就是说这样的一个集合

是由题目事先确定好的

在中间运行的当中是不会改变的

可是我们对照的八皇后发现

对于这个问题

它的首先上来

每一个位置都是可以选择的

并没有一个特定的限制

其次呢它的这个

放棋子的过程当中

这个性质的条件

它其实是有一个变化的过程

这是它们一个很重要的区别

那好 经过这样的分析

下面我们就来看看

怎么样来求解这两个问题

我们今天是尝试着要把两个

看上去不一样但是呢

有类似有共同性的题目放到一起

来看它们解题的思路

那很显然

对于求解分书 八皇后

这两个问题它的关键点

根据我们前面几章的学习

我们知道在计算机里头

一个很重要的求解问题的方法

就是使用枚举法

而我们这两个问题

分书也好

八皇后也好

它恰恰就是在问大家

到底有多少种方案

那样的一些书和那样的一个棋盘

你的的确确是有很很多种的分配方法

和放棋子的方法

那到底那一个是合理的呢

到底那一个能满足题目的要求呢

而这其实很容易想到的一个解题思路

就是枚举的方法

我依次的去把所以的方案都枚举出来

然后去看

看它们是不是满足条件

所以这个问题的关键是

你怎么能够

或者说如何

把可能的方案依次的枚举出来

那这里头我们考虑到

由于在这两个问题里头

都是行跟列

不能出现重复的元素

也就是说只能放一个元素在里头

所以呢

我们这样的一个问题

根据这个特定的性质

我们马上应该就能想到

可以把这个问题的求解

这个分解为

把它逐行来求

当然了逐列也是一样的

这个矩阵其实是

你可以在那转换一下

我们后面说行说列其实在实现程序的时候

这两种都是可行的

那么我们讲的时候可能就按行来说

分解成一行一行来求解

比方说分书

这一行代表一个人的话

那我就是一个人一个人的

给它书

八皇后 是吧

那我就一行一行

去在行上面去找到棋子(皇后)的位置

那也就是说这个问题的求解过程

就变成了

依次来确定

在每一行上面

这个元素的列位置

就是 我第一行完成了

我就不管了

然后就去弄第二行

然后弄第三行

直到5行这个分书类题

或者8行这个皇后类题

都把它处理完这个任务就完成了

所以这个时候我们原来的一个大问题

就变成了一个小问题

或者变成了5个或者8个小问题的求解

什么小问题呢

就是在一行上面

去找到一个合适的位置

去分一本书

或者呢放一个八皇后

也就是依次去确定

每行上面元素的

存放的列的位置

同时 还是由于这个行跟列

它不能重复

这样的一个要求

也就是说在每次确定了

一行上的元素之后

其实这一个相应的行或者是列

你这个元素肯定是

出现在每一行每一列的矩阵里头嘛

其实是可以理解为

可以把它们删掉

也就是说

我们发现去确定任意行上的

这个元素的位置

这样的一个过程

当我们删掉这行跟列之后

那么其实它变成了一个更小的矩阵

也就是说对于剩下的问题的求解

就变成了一个小了一些规模的

行跟列各减去1的一个新的矩阵

在里头去填元素

那么根据我们前面讲过的

这不又是一个同样的问题的再现吗

只不过这个时候问题的规模缩小了

原来是5本书5个人

由于你已经搞定一个人跟一本书了

所以呢就剩下4个人4本书

八皇后也是一样

我已经放上去一个棋子了

那就变成了一个7*7的棋盘上面

放7个皇后

这个问题就变得

跟原来的问题n*n不太一样

它缩小了

可是呢

它的这个思路

很显然又是可以运用同样的办法去求解的

所以这个里头我们就再一次的看到

当我们这么做了之后其实

很容易想到

递归是解决这两个问题的

很重要的切入点或者手段

那么当我们逐行去求解的时候

我们进一步来看

这一行一个人我要去分5本书

或者这一行八个皇后

我放到那一列上面去呢

这个里头有5个或者8个

这样的一个选择

那么到底应该选择那一列呢

很显然 每一列都有可能

这个地位是平等的

我们前面说每一行是把这个任务

承担了一个任务的子任务

一步一步来做的

每一行就是一步

那么现在每一列

其实是每一个你都有去尝试的

你尝试完了你才能综合起来

哪些列是可能满足条件的

因为我们题目要求所有的方案

所有很有可能 某些列都有可能是对的

这个时候它列跟列的关系

跟行跟行的关系不太一样

所以我们对于每一行

去列举里头的每一列

去枚举它 去尝试的时候

每一列都有可能所以这个地方

我们需要循环对每一列进行尝试

无论是分书这一行有5本书我要分给这个人

到底那本书分给他呢

挑选其中的一列代表这本书分给了他

皇后也是一样

每一列我们都要去为它尝试

那么基于这样的考虑

我们进一步来考虑

在题目里头的这个条件限制

对于题目里头

设置要求的元素的摆放是有条件限制的

当前行的一种决策

这本书

现在这个人已经占了第三本书

那就意味着

虽然第四个人可能也喜欢第三本书

但是呢已经轮不到第四个人了

因为这第一个人已经把第三本书占掉了

这其实就意味着当前行

你做的这个决策

在哪一个列上面去放一个元素

是会改变或者呢

是会影响后者的选择过程的

因此啊

一方面我们需要在每一次的决策之后

因为你要影响后面嘛

所以我要去更新或者调整这个限制条件

比方说一个空空的棋盘

你其实刚开始放第一个棋子的时候

是可以任意放的

但是这一个棋子落下去

立刻的这个对角线就不能再占了

对不对

那么其实就把

对角线这个棋盘上的位置

就等于挖出去了

那原来我是禁止这个行跟列的

或者说我原来没有棋子的时候

是空棋盘可以任意放

由于你放上去一个棋子

就导致你不能再任意去放

你受到了新的约束和限制

所以我们说

当你当前行的决策完成了之后

需要去把整个去找这个方案的后续的过程

它的限制条件

进行跟新 进行改变

那么另一个方面呢

我们也需要在进行

另外一个列的尝试的时候

要把这个限制条件呢

要恢复到这个前一列决策时候的状态

什么意思呢

就是我刚才说过了

我们的每一列其实是对等的

也就是平等的地位

每一列都要独立的去尝试

那么既然是平等的

那就意味着

在每一列去尝试的时候

它们的前提条件必须是一模一样的

大家从同一个起跑线上出发

可是我们别忘了

我们的程序是顺序执行的

当我们依次去枚举

哪一列是对或者是不对的时候

其实总有一些列是新做的

总有一些列是后做的

那么后做的列

我们怎么能够保证

它跟前面

那个排在前面去尝试的那个列

它的地位是对等的呢

它们的起始条件是一样的呢

当然得靠我们的程序代码去考证

可是我们前面刚刚说过

你每一次做了决策

就是我前面说 这个地方不错

这一列可以选择它

当我们去做这个决策的时候

为了去做后面的行

注意我们当前行

选择的某一列

我们为了去做后面那一行

就是下一个子任务的

工作的时候

我们是需要去

更新那个限制条件的

但是呢

当你做了这样的限制之后

等到后续的事情做完了

要退回去

去尝试当前行的下一列的时候

这个时候就出现了一个问题

就是你下一列需要去跟

前一列它的初始条件是一致的

所以呢

我们这个里头就是说

当我们进行另一列的尝试的时候

需要把限制条件恢复过来

那么具体怎么做

我们后面结合代码来把这个抽象的说法呢

具体化一些

那么这样的一种恢复到上次枚举之前的

条件限制的操作的步骤

我们就把它称为回溯

这个有点像电视剧里头

时光机的时光倒流到过去的某种状态

从头开始

这是我们一个基本的一个思路

也就是一行一行的去尝试

去完成这个任务

在每一行里头呢

一列一列的去尝试它

当我们确定去尝试某个列的时候

做出某种决策的时候

这个任务就缩小了

我们可以用递归的方法来去求解它

程序设计基础课程列表:

第一章 编程初步

-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 实现程序功能

-程设论道

--程设论道

-师生问答

--师生问答

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

5.4.3 问题分析——区别笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。